You are given an array nums that consists of positive integers.
The GCD of a sequence of numbers is defined as the greatest integer that divides all the numbers in the sequence evenly.
[4,6,16] is 2.A subsequence of an array is a sequence that can be formed by removing some elements (possibly none) of the array.
[2,5,10] is a subsequence of [1,2,1,2,4,1,5,10].Return the number of different GCDs among all non-empty subsequences of nums.
Example 1:
Input: nums = [6,10,3] Output: 5 Explanation: The figure shows all the non-empty subsequences and their GCDs. The different GCDs are 6, 10, 3, 2, and 1.
Example 2:
Input: nums = [5,15,40,5,6] Output: 7
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 2 * 105The key insight is that instead of generating all subsequences, we can reason about possible GCD values. Let maxVal be the maximum number in the array. For every potential GCD candidate g from 1 to maxVal, check whether there exists a subsequence whose GCD equals g.
To do this efficiently, iterate through all multiples of g present in the array. Maintain a running gcd of these multiples. If the cumulative GCD eventually becomes exactly g, then some subsequence formed by those numbers has GCD g, and we count it as a valid result.
This works because any subsequence with GCD g must consist of numbers divisible by g. Using a presence array or set allows quick checks for multiples. The algorithm avoids exponential subsequence generation and leverages number theory properties of GCD.
Time Complexity: roughly O(maxVal log maxVal) due to iterating multiples and computing GCDs. Space Complexity: O(maxVal) for tracking number presence.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterate Possible GCD Values with Multiples Scan | O(M log M) | O(M) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Think of how to check if a number x is a gcd of a subsequence.
If there is such subsequence, then all of it will be divisible by x. Moreover, if you divide each number in the subsequence by x , then the gcd of the resulting numbers will be 1.
Adding a number to a subsequence cannot increase its gcd. So, if there is a valid subsequence for x , then the subsequence that contains all multiples of x is a valid one too.
Iterate on all possiblex from 1 to 10^5, and check if there is a valid subsequence for x.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Any subsequence with GCD g must consist only of numbers divisible by g. Therefore, checking multiples of g ensures we only consider numbers that could contribute to a subsequence whose GCD equals g.
Yes, problems involving GCD properties, number theory, and optimized counting frequently appear in FAANG-style interviews. This question tests mathematical insight, efficient iteration, and understanding of GCD behavior.
A boolean presence array or hash set is commonly used to mark which numbers exist in the input. This allows efficient lookup while iterating through multiples of each potential GCD value.
The optimal strategy is to iterate over every possible GCD candidate from 1 to the maximum value in the array and check its multiples. By computing the running GCD of those multiples that appear in the array, we can determine whether a subsequence exists with that exact GCD.