# Number of Different Subsequences GCDs **Difficulty:** HARD [External](https://leetcode.com/problems/number-of-different-subsequences-gcds) Canonical: https://scaleengineer.com/dsa/problems/number-of-different-subsequences-gcds **Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Counting](https://scaleengineer.com/dsa/patterns/counting), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory) **Data structures:** Array **Companies:** [Akuna Capital](https://scaleengineer.com/companies/akuna-capital) --- ## Problem 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. * For example, the GCD of the sequence `[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. * For example, `[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:** ![](https://assets.glich.co/dsa/number-of-different-subsequences-gcds/image0.png) **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 <= 105` * `1 <= nums[i] <= 2 * 105` # Approaches ## Naive Iteration over all Potential GCDs A straightforward but inefficient approach is to check for every possible integer `k`, whether it can be the GCD of some subsequence. The possible values for a GCD are limited by the maximum value in the input array `nums`. For each potential GCD `k`, we can form a subsequence by picking all numbers from `nums` that are multiples of `k`. If this subsequence is non-empty, we compute its GCD. If the result is exactly `k`, then `k` is a valid GCD, and we count it. **Time:** O(M * N * log(M)), where `N` is the length of `nums` and `M` is the maximum value in `nums`. The outer loop runs `M` times. Inside, we iterate through `N` numbers, and computing the GCD of up to `N` numbers takes `O(N * log(M))`. This is too slow for the given constraints. · **Space:** O(1) if we don't count the storage for multiples, or O(N) if we store them in a list for each potential GCD, where N is the number of elements in `nums`. **Pros:** Simple to understand and implement.; Correctly solves the problem without complex data structures. **Cons:** Highly inefficient due to nested loops over potential GCDs and the entire input array.; Will result in a 'Time Limit Exceeded' error for the given constraints. ### Explanation The logic is based on the definition of a subsequence GCD. For any number `k` to be the GCD of a subsequence, there must exist a set of numbers in the original array `nums` such that: 1. All numbers in the set are multiples of `k`. 2. The greatest common divisor of all numbers in the set is exactly `k`. This approach directly translates this logic into code. We iterate through all possible GCD values `k` from 1 up to the maximum element in `nums`. For each `k`, we scan the entire `nums` array, collect all multiples of `k`, and then compute their GCD. If this GCD equals `k`, we've found a valid subsequence GCD. ```java class Solution { private int gcd(int a, int b) { while (b != 0) { int temp = b; b = a % b; a = temp; } return a; } public int countDifferentSubsequenceGCDs(int[] nums) { int maxVal = 0; for (int num : nums) { maxVal = Math.max(maxVal, num); } int count = 0; for (int i = 1; i <= maxVal; i++) { // Find the GCD of all numbers in nums that are multiples of i int currentGcd = 0; for (int num : nums) { if (num % i == 0) { if (currentGcd == 0) { currentGcd = num; } else { currentGcd = gcd(currentGcd, num); } } } // If the computed GCD is i, then i is a valid subsequence GCD if (currentGcd == i) { count++; } } return count; } } ``` ### Algorithm - Find the maximum value `maxVal` in the input array `nums`. - Initialize a counter `count` to 0. - Iterate `k` from 1 to `maxVal`. This `k` is a potential GCD. - For each `k`, create a temporary list of all numbers in `nums` that are multiples of `k`. - If this list of multiples is not empty, compute the GCD of all numbers in it. - If the computed GCD is equal to `k`, it means `k` is a valid subsequence GCD. Increment `count`. - After iterating through all possible `k`, return the total `count`. ## Optimized Approach by Iterating Over Multiples This approach improves upon the naive one by optimizing the search for multiples. Instead of iterating through the entire `nums` array for each potential GCD `k`, we first mark all numbers from `nums` in a boolean `present` array. Then, for each `k`, we iterate only through its multiples (`k, 2k, 3k, ...`) and check their presence in the map. This avoids the costly `O(N)` scan for each `k` and makes the solution efficient enough to pass within the time limits. **Time:** O(M * log(M) * log(M)), where `M` is the maximum value in `nums`. The total number of iterations of the inner loop across all `i` is given by the harmonic series sum `M/1 + M/2 + ... + M/M`, which is `O(M * log(M))`. Each step in the inner loop involves a GCD operation, which takes `O(log(M))`. Thus, the total complexity is `O(M * log^2(M))`. · **Space:** O(M), where `M` is the maximum value in `nums`. This is for the `present` boolean array. **Pros:** Significantly more efficient than the naive approach.; Passes within the time limits for the given constraints.; The logic is a clever and direct application of number theory properties. **Cons:** Requires extra space proportional to the maximum value in `nums`, which could be large. ### Explanation The core idea remains the same: a number `k` is a valid subsequence GCD if the GCD of all numbers in `nums` that are multiples of `k` is exactly `k`. The key optimization is how we find these multiples and compute their GCD. 1. First, we determine the maximum value `maxVal` in `nums` and create a boolean array `present` of size `maxVal + 1`. We populate this array by iterating through `nums`, so `present[x]` is true if `x` is in `nums`. 2. Then, we iterate `i` from 1 to `maxVal`. For each `i`, we want to find the GCD of its multiples present in `nums`. 3. Instead of scanning `nums`, we scan through the multiples of `i` directly: `j = i, 2*i, 3*i, ...` up to `maxVal`. 4. For each `j`, we check `present[j]`. If it's true, we update the GCD for the current `i`. 5. If, after checking all multiples, the calculated GCD is equal to `i`, we've found a new distinct subsequence GCD. An additional small optimization is that during the calculation of the GCD for `i`, if the `currentGcd` becomes equal to `i`, we can stop early, as it's the smallest possible non-zero GCD we can get (since all numbers are multiples of `i`). ```java class Solution { private int gcd(int a, int b) { // Handle gcd(0, x) = x if (a == 0) return b; while (b != 0) { int temp = b; b = a % b; a = temp; } return a; } public int countDifferentSubsequenceGCDs(int[] nums) { int maxVal = 0; for (int num : nums) { maxVal = Math.max(maxVal, num); } boolean[] present = new boolean[maxVal + 1]; for (int num : nums) { present[num] = true; } int count = 0; for (int i = 1; i <= maxVal; i++) { int currentGcd = 0; // Iterate through multiples of i for (int j = i; j <= maxVal; j += i) { if (present[j]) { currentGcd = gcd(currentGcd, j); } // Optimization: if we've already found a GCD of i, // no smaller GCD is possible for this subsequence. if (currentGcd == i) { break; } } if (currentGcd == i) { count++; } } return count; } } ``` ### Algorithm - Find the maximum value `maxVal` in `nums`. - Create a boolean array `present` of size `maxVal + 1` to mark which numbers are present in the input array. This allows for O(1) lookups. - Initialize a `count` of different GCDs to 0. - Iterate with a variable `i` from 1 to `maxVal`. This `i` represents a potential GCD. - For each `i`, find the GCD of all its multiples that are present in `nums`. To do this, iterate `j` from `i` to `maxVal` with a step of `i` (`j = i, 2i, 3i, ...`). - If `present[j]` is true, update the `currentGcd` for `i` with `j`. - If the final `currentGcd` for `i` is equal to `i`, it means `i` is a valid subsequence GCD, so increment `count`. - Return the total `count`. # Solutions ### Java ```java class Solution { public int countDifferentSubsequenceGCDs(int[] nums) { int mx = Arrays.stream(nums).max().getAsInt(); boolean[] vis = new boolean[mx + 1]; for (int x : nums) { vis[x] = true; } int ans = 0; for (int x = 1; x <= mx; ++x) { int g = 0; for (int y = x; y <= mx; y += x) { if (vis[y]) { g = gcd(g, y); if (x == g) { ++ans; break; } } } } return ans; } private int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } } ``` ### CPP ```cpp class Solution { public: int countDifferentSubsequenceGCDs(vector &nums) { int mx = *max_element(nums.begin(), nums.end()); vector vis(mx + 1); for (int &x : nums) { vis[x] = true; } int ans = 0; for (int x = 1; x <= mx; ++x) { int g = 0; for (int y = x; y <= mx; y += x) { if (vis[y]) { g = gcd(g, y); if (g == x) { ++ans; break; } } } } return ans; } }; ``` ### Python ```python class Solution: def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int: mx = max(nums) vis = set(nums) ans = 0 for x in range(1, mx + 1): g = 0 for y in range(x, mx + 1, x): if y in vis: g = gcd(g, y) if g == x: ans += 1 break return ans ```