Minimum subsequence length for array LCM
Filed under Infosys
Free read 3 of 3Find 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
Find overall LCM L. Each prime factor power p^k dividing L must be satisfied by at least one element in the chosen subsequence.
Map prime power requirements to elements. Select the smallest set of elements covering all max prime power requirements.
Use dynamic programming over prime factor states or BFS to find minimum subset length.
Solution
O(N * K) time where K is number of distinct sub-LCM values, O(K) space
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.