← Infosys questions

Minimum subsequence length for array LCM

Filed under Infosys

Free read 3 of 3

Find overall LCM L. Each prime factor power p^k dividing L must be satisfied by at least one element in the chosen subsequence.

The question

Given an array of positive integers nums of size N, calculate the Least Common Multiple (LCM) of all elements in the entire array, denoted as L. Find the minimum size of a subsequence of nums whose LCM is equal to L.

Constraints

  • 1 <= N <= 100
  • 1 <= nums[i] <= 10^9

Examples

Input
nums = [2, 3, 6]
Output
1
Why
The overall LCM of [2, 3, 6] is 6. Subsequence [6] has LCM equal to 6, so length is 1.
Input
nums = [2, 3, 5]
Output
3
Why
The overall LCM is 30. No proper subsequence yields LCM 30, so all 3 elements are needed.

Approach

  1. Find overall LCM L. Each prime factor power p^k dividing L must be satisfied by at least one element in the chosen subsequence.

Solution

O(N * K) time where K is number of distinct sub-LCM values, O(K) space

Python
import math

def lcm(a, b):
    return (a * b) // math.gcd(a, b)

class Solution:
    def minSubsequenceForLCM(self, nums: list[int]) -> int:
        total_lcm = 1
        for x in nums:
            total_lcm = lcm(total_lcm, x)
        
        # BFS over reachable LCM values to find minimum length
        dp = {1: 0}
        for x in nums:
            curr_states = list(dp.items())
            for val, steps in curr_states:
                nxt = lcm(val, x)
                if nxt not in dp or dp[nxt] > steps + 1:
                    dp[nxt] = steps + 1
        return dp[total_lcm]

Tips

  • What they are testing: Test cases where single elements equal the entire array's LCM to achieve minimum output 1.
  • Common mistake: Brute-forcing all 2^N subsequences without prime factorization analysis, causing Time Limit Exceeded.

Related Infosys questions

Collected from public candidate posts and coding forums. Updated Nov 2026.