Number of Different Subsequences GCDs

Number of Different Subsequences GCDs

What is this problem about?

The Number of Different Subsequences GCDs problem asks: given an integer array, how many distinct GCD values can any non-empty subsequence of the array produce? This hard coding problem uses a math insight: for each candidate GCD value g, check whether any subsequence has GCD exactly g by tracking the GCD of elements divisible by g.

Why is this asked in interviews?

Akuna Capital asks this hard number theory problem because the naive O(2^n) approach (check all subsequences) is infeasible. The key insight — iterating over all possible GCDs from 1 to max(nums) and verifying existence — reduces it to O(max * log(max)) using the harmonic series property. The array, math, number theory, and counting interview pattern is the core.

Algorithmic pattern used

GCD enumeration with divisor tracking. For each candidate GCD g from 1 to max(nums): compute the GCD of all elements in nums that are divisible by g. If this computed GCD equals g exactly, then g is achievable. Count how many g values are achievable. The GCD computation over divisible elements converges in O(log(max)) steps.

Example explanation

nums=[6,10,3]. Max=10. For each g:

• g=1: elements divisible by 1 → all. GCD(6,10,3)=1=g ✓.
• g=2: elements: 6,10. GCD(6,10)=2=g ✓.
• g=3: elements: 6,3. GCD(6,3)=3=g ✓.
• g=6: elements: 6. GCD(6)=6=g ✓.
• g=10: elements: 10. GCD(10)=10=g ✓. Distinct GCDs = 5.

Common mistakes candidates make

• Generating all subsequences (exponential time).
• Not understanding why checking divisibility by g covers all subsequence GCDs.
• Incorrect GCD computation accumulation (must use running GCD correctly).
• Not iterating all g from 1 to max(nums) (missing some possible GCD values).

Interview preparation tip

"Count distinct subsequence GCDs" reduces to: for each g, can we form a subsequence whose GCD = g? Answer: yes iff gcd of all multiples of g in the array = g. This GCD-over-multiples technique is a number theory trick worth memorizing. Practice similar problems: "count subsequences with LCM equal to x." Understanding how GCD/LCM interact with subsets is a high-value number theory skill for Akuna Capital and similar firms.