Number of Different Subsequences GCDs

Hard

#1663Time: 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`.1 company

Patterns

Math Counting Number Theory

Data structures

Array

Companies

Akuna Capital

Prompt

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:

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 <= 10⁵
1 <= nums[i] <= 2 * 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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:

All numbers in the set are multiples of k.
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.

1class Solution {2    private int gcd(int a, int b) {3        while (b != 0) {4            int temp = b;5            b = a % b;6            a = temp;7        }8        return a;9    }10 11    public int countDifferentSubsequenceGCDs(int[] nums) {12        int maxVal = 0;13        for (int num : nums) {14            maxVal = Math.max(maxVal, num);15        }16 17        int count = 0;18        for (int i = 1; i <= maxVal; i++) {19            // Find the GCD of all numbers in nums that are multiples of i20            int currentGcd = 0;21            for (int num : nums) {22                if (num % i == 0) {23                    if (currentGcd == 0) {24                        currentGcd = num;25                    } else {26                        currentGcd = gcd(currentGcd, num);27                    }28                }29            }30            31            // If the computed GCD is i, then i is a valid subsequence GCD32            if (currentGcd == i) {33                count++;34            }35        }36        return count;37    }38}

Complexity

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`.

Trade-offs

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.

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.

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.

Walkthrough

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.

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.
Then, we iterate i from 1 to maxVal. For each i, we want to find the GCD of its multiples present in nums.
Instead of scanning nums, we scan through the multiples of i directly: j = i, 2*i, 3*i, ... up to maxVal.
For each j, we check present[j]. If it's true, we update the GCD for the current i.
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).

1class Solution {2    private int gcd(int a, int b) {3        // Handle gcd(0, x) = x4        if (a == 0) return b;5        while (b != 0) {6            int temp = b;7            b = a % b;8            a = temp;9        }10        return a;11    }12 13    public int countDifferentSubsequenceGCDs(int[] nums) {14        int maxVal = 0;15        for (int num : nums) {16            maxVal = Math.max(maxVal, num);17        }18 19        boolean[] present = new boolean[maxVal + 1];20        for (int num : nums) {21            present[num] = true;22        }23 24        int count = 0;25        for (int i = 1; i <= maxVal; i++) {26            int currentGcd = 0;27            // Iterate through multiples of i28            for (int j = i; j <= maxVal; j += i) {29                if (present[j]) {30                    currentGcd = gcd(currentGcd, j);31                }32                // Optimization: if we've already found a GCD of i,33                // no smaller GCD is possible for this subsequence.34                if (currentGcd == i) {35                    break;36                }37            }38            if (currentGcd == i) {39                count++;40            }41        }42        return count;43    }44}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int countDifferentSubsequenceGCDs(int[] nums) {4    int mx = Arrays.stream(nums).max().getAsInt();5    boolean[] vis = new boolean[mx + 1];6    for (int x : nums) {7      vis[x] = true;8    }9    int ans = 0;10    for (int x = 1; x <= mx; ++x) {11      int g = 0;12      for (int y = x; y <= mx; y += x) {13        if (vis[y]) {14          g = gcd(g, y);15          if (x == g) {16            ++ans;17            break;18          }19        }20      }21    }22    return ans;23  }24private25  int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }26}

1class Solution {2public:3  int countDifferentSubsequenceGCDs(vector<int> &nums) {4    int mx = *max_element(nums.begin(), nums.end());5    vector<bool> vis(mx + 1);6    for (int &x : nums) {7      vis[x] = true;8    }9    int ans = 0;10    for (int x = 1; x <= mx; ++x) {11      int g = 0;12      for (int y = x; y <= mx; y += x) {13        if (vis[y]) {14          g = gcd(g, y);15          if (g == x) {16            ++ans;17            break;18          }19        }20      }21    }22    return ans;23  }24};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem