Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1819. Number of Different Subsequences GCDs - Leetcode Solution

Code Implementation

from math import gcd
class Solution:
    def countDifferentSubsequenceGCDs(self, nums):
        max_num = max(nums)
        nums_set = set(nums)
        ans = 0
        for x in range(1, max_num + 1):
            g = 0
            for y in range(x, max_num + 1, x):
                if y in nums_set:
                    g = gcd(g, y)
                if g == x:
                    break
            if g == x:
                ans += 1
        return ans
      
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;

class Solution {
public:
    int countDifferentSubsequenceGCDs(vector<int>& nums) {
        int max_num = *max_element(nums.begin(), nums.end());
        unordered_set<int> nums_set(nums.begin(), nums.end());
        int ans = 0;
        for (int x = 1; x <= max_num; ++x) {
            int g = 0;
            for (int y = x; y <= max_num; y += x) {
                if (nums_set.count(y)) {
                    g = __gcd(g, y);
                }
                if (g == x) break;
            }
            if (g == x) ++ans;
        }
        return ans;
    }
};
      
import java.util.*;
class Solution {
    public int countDifferentSubsequenceGCDs(int[] nums) {
        int maxNum = 0;
        for (int n : nums) maxNum = Math.max(maxNum, n);
        Set<Integer> set = new HashSet<>();
        for (int n : nums) set.add(n);
        int ans = 0;
        for (int x = 1; x <= maxNum; x++) {
            int g = 0;
            for (int y = x; y <= maxNum; y += x) {
                if (set.contains(y)) {
                    g = gcd(g, y);
                }
                if (g == x) break;
            }
            if (g == x) ans++;
        }
        return ans;
    }
    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}
      
var countDifferentSubsequenceGCDs = function(nums) {
    const maxNum = Math.max(...nums);
    const numsSet = new Set(nums);
    let ans = 0;
    const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);
    for (let x = 1; x <= maxNum; x++) {
        let g = 0;
        for (let y = x; y <= maxNum; y += x) {
            if (numsSet.has(y)) {
                g = gcd(g, y);
            }
            if (g === x) break;
        }
        if (g === x) ans++;
    }
    return ans;
};

Problem Description

You are given an array nums of positive integers. A subsequence of nums is any sequence that can be derived from nums by deleting some or no elements without changing the order of the remaining elements. For each possible non-empty subsequence, calculate its greatest common divisor (GCD). Your task is to count how many different GCDs can be obtained from all possible non-empty subsequences of nums.
  • Each subsequence can use elements from nums only once and must keep their original order.
  • Return the number of distinct GCDs among all possible non-empty subsequences.

Thought Process

The brute-force approach would be to generate all possible subsequences, compute the GCD for each, and count the number of distinct GCDs. However, this is computationally infeasible for large arrays, as the number of subsequences grows exponentially with the size of nums. Instead, we notice that:
  • If a number x is the GCD of some subsequence, then there must exist at least two or more elements in nums that are multiples of x whose GCD is exactly x.
  • For every possible integer x from 1 up to the maximum element in nums, we can check if there is a subsequence whose GCD is x by looking at all multiples of x in nums and computing their GCD.
This insight allows us to avoid generating all subsequences and instead check for each possible GCD directly.

Solution Approach

The optimized solution uses the following steps:
  1. Find the maximum value max_num in nums.
  2. Store all numbers in a set for O(1) lookup.
  3. For each possible GCD value x from 1 to max_num:
    • Initialize a variable g = 0 to represent the running GCD.
    • For every multiple y of x (i.e., y = x, 2x, 3x, ... up to max_num):
      • If y is in nums, update g = gcd(g, y).
      • If at any point g becomes equal to x, break early (since further GCDs can't reduce it below x).
    • If after the loop, g == x, then x is a valid GCD for some subsequence, so increment the answer.
  4. Return the total count of valid GCDs found.
This approach leverages the mathematical property that the GCD of a set of multiples of x can only be x or greater, and efficiently checks each candidate.

Example Walkthrough

Consider nums = [6, 10, 3].
  • Maximum value is 10.
  • We check all possible GCDs from 1 to 10.
  • For x = 2:
    • Multiples are 2, 4, 6, 8, 10.
    • 6 and 10 are in nums. GCD(0,6)=6, GCD(6,10)=2. Now g==2, so x=2 is a possible GCD.
  • For x = 3:
    • Multiples are 3, 6, 9.
    • 3 and 6 are in nums. GCD(0,3)=3, GCD(3,6)=3. So x=3 is a possible GCD.
  • For x = 5:
    • Multiples are 5, 10.
    • Only 10 is in nums. GCD(0,10)=10, which is not 5.
  • Continue similarly for x=1 to x=10. The valid GCDs are 1, 2, 3, 6, 10.
The answer is 5.

Time and Space Complexity

  • Brute-force: Generating all subsequences is O(2^n), which is infeasible for n up to 105.
  • Optimized approach:
    • We iterate through all possible GCDs (from 1 to max_num), and for each, check its multiples up to max_num.
    • This is approximately O(max_num * log(max_num)), since the inner GCD calculation is logarithmic, and there are at most O(max_num) outer iterations.
    • Space complexity is O(max_num) due to the set for quick lookup.
This makes the solution efficient even for large input sizes.

Summary

The key insight is that instead of examining every subsequence, we can efficiently check for each possible GCD by considering all its multiples in the array. This transforms an exponential problem into a tractable one using mathematical properties of the GCD. The solution is both elegant and efficient, leveraging sets for fast lookups and the properties of divisibility and GCD.