Watch 10 video solutions for Number of Different Subsequences GCDs, a hard level problem involving Array, Math, Counting. This walkthrough by code Explainer has 2,051 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 * 105Problem Overview: Given an integer array nums, count how many distinct values can appear as the GCD of some non‑empty subsequence. You do not need to generate subsequences explicitly. The goal is to determine how many integers g exist such that some subset of numbers in nums has gcd = g.
Approach 1: Direct Counting of GCD Divisors (O(M log M) time, O(M) space)
This approach leverages the mathematical structure of GCDs. Instead of enumerating subsequences, iterate candidate GCD values from 1 to max(nums). For each candidate g, check all multiples of g that appear in the array. Maintain a running GCD of these multiples using the Euclidean algorithm. If the accumulated GCD becomes exactly g, then there exists a subsequence whose GCD is g. A boolean presence array or hash set allows O(1) membership checks for multiples. This transforms the exponential subsequence search into a number‑theory iteration over multiples. The runtime is roughly proportional to the harmonic series over multiples, giving O(M log M) time where M = max(nums), and O(M) extra space. This method relies heavily on concepts from number theory and efficient gcd computation.
Approach 2: Efficient Multiple Checking Using Direct Subsequence Logic (O(M log M) time, O(M) space)
This strategy focuses on checking whether a target value can be formed as the GCD of some subsequence by examining its multiples. Store all array values in a fast lookup structure such as a boolean array. For each potential GCD x, iterate through multiples x, 2x, 3x... up to max(nums). If a multiple exists in the array, merge it into a running GCD calculation. The moment the running value equals x, you know a subsequence can produce that GCD, so you increment the answer and stop scanning further multiples. The key insight: if the GCD of several multiples equals x, some subsequence among them must produce that value. This approach avoids generating combinations entirely and turns the problem into structured iteration over multiples. The technique is common in math-driven array problems and uses simple presence checks over the array.
Recommended for interviews: Interviewers typically expect the multiple‑checking GCD approach. A brute subsequence enumeration quickly becomes infeasible because the number of subsequences is 2^n. Demonstrating the insight that every valid GCD must divide at least one array element shows strong algorithmic thinking and familiarity with number theory optimizations. The optimal solution runs in near linear time relative to the maximum value in the array, which is the key observation interviewers look for.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Counting of GCD Divisors | O(M log M) | O(M) | General case when max value is manageable and you want a clean number‑theory approach |
| Efficient Multiple Checking Using Direct Subsequence | O(M log M) | O(M) | Interview‑preferred approach; avoids subsequence generation and uses GCD accumulation |