Skip to content
← All posts

Number of Different Subsequences GCDs: Enumerate Candidate GCDs

4 min read
leetcodeproblemhardarraysmath

LeetCode 1819. Number of Different Subsequences GCDs asks you to find how many distinct GCD values are possible across all non-empty subsequences of a given array of positive integers. A subsequence can skip elements but must preserve relative order, and the GCD of a sequence is the largest integer that evenly divides every element.

For example, given nums = [6, 10, 3], the non-empty subsequences and their GCDs are:

  • [6] with GCD 6, [10] with GCD 10, [3] with GCD 3
  • [6, 10] with GCD 2, [6, 3] with GCD 3, [10, 3] with GCD 1
  • [6, 10, 3] with GCD 1

The distinct GCD values are {1, 2, 3, 6, 10}, so the answer is 5.

nums = [6, 10, 3]Input array:6103All non-empty subsequences and their GCDs:[6]GCD = 6[10]GCD = 10[3]GCD = 3[6, 10]GCD = 2[6, 3]GCD = 3[10, 3]GCD = 1[6, 10, 3]GCD = 1Distinct GCD values found:123610Answer = 5
Seven subsequences produce five distinct GCD values. Enumerating all 2^n subsequences is too slow for large arrays, so we need a smarter approach.

The approach

There are up to 2^n non-empty subsequences, so brute-forcing every one is not feasible when n can be as large as 200,000. Instead, you can flip the question around: for each candidate GCD value g from 1 to max(nums), ask whether g is actually achievable by some subsequence.

To check if g is achievable, iterate through all multiples of g (that is, g, 2g, 3g, and so on up to max(nums)). For each multiple that exists in the array, fold it into a running GCD. If the running GCD ever reaches exactly g, then some subsequence of the array elements that are multiples of g has GCD equal to g, and you count it.

Why does this work? Any subsequence whose GCD is g must consist entirely of multiples of g. So you only need to consider the array elements that are multiples of g. If the GCD of all those elements is exactly g, then g is achievable. If their GCD is some value larger than g (which would itself be a multiple of g), then no subset of them can produce a GCD of exactly g.

The total work across all candidates is proportional to max_val * (1/1 + 1/2 + ... + 1/max_val), which is O(max_val * log(max_val)). This harmonic series bound makes the algorithm efficient even when max_val is up to 200,000.

The code

from math import gcd
from typing import List

class Solution:
    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:
        num_set = set(nums)
        max_val = max(nums)
        count = 0

        for g in range(1, max_val + 1):
            current_gcd = 0
            for multiple in range(g, max_val + 1, g):
                if multiple in num_set:
                    current_gcd = gcd(current_gcd, multiple)
                    if current_gcd == g:
                        break
            if current_gcd == g:
                count += 1

        return count

Here is what happens step by step:

  1. Build a set from nums so you can check membership in O(1).
  2. Find max_val, the largest number in the array.
  3. For each candidate g from 1 to max_val, walk through every multiple of g up to max_val.
  4. Whenever a multiple is found in the set, update the running GCD with gcd(current_gcd, multiple).
  5. If the running GCD equals g, break early and increment the count.
  6. Return the total count of achievable GCD values.
Practice GCD and number theory patterns

Visual walkthrough

Here is the candidate-by-candidate process for nums = [6, 10, 3]:

Step 1: Store array elements in a set for O(1) lookup

nums = [6, 10, 3]num_set = {3, 6, 10}, max_val = 10

We need to quickly check whether a particular number exists in nums. A set gives us constant-time membership tests.

Step 2: Candidate g = 1. Check multiples 1, 2, 3, ..., 10

Multiples of 1: 1, 2, 3, 4, 5, 6, 7, 8, 9, 1012345678910GCD(3, 6, 10) = 1 = g. Count += 1

We find 3 in the set (running GCD = 3), then 6 (GCD(3,6) = 3), then 10 (GCD(3,10) = 1). The running GCD reached 1, so g = 1 is achievable.

Step 3: Candidate g = 2. Check multiples 2, 4, 6, 8, 10

Multiples of 2: 2, 4, 6, 8, 10246810GCD(6, 10) = 2 = g. Count += 1

We find 6 in the set (running GCD = 6), then 10 (GCD(6,10) = 2). The running GCD reached 2, so g = 2 is achievable.

Step 4: Candidate g = 3. Check multiples 3, 6, 9

Multiples of 3: 3, 6, 9369GCD(3) = 3 = g. Count += 1 (early stop)

We find 3 in the set (running GCD = 3). The running GCD already equals g, so we can stop early. g = 3 is achievable.

Step 5: Candidates g = 4 and g = 5 both fail

g = 4: multiples 4, 8 (none in set)No multiples of 4 found. Skip.g = 5: multiples 5, 10. Found 10. GCD(10) = 10, not 5.Running GCD never reached 5. Skip.

For g = 4, the only multiple in the set is 8? No, none of 4, 8 are present. For g = 5, the multiple 10 is present, but GCD(10) = 10 which is not 5. Neither candidate is achievable.

Step 6: Candidates g = 6 through g = 10

g=66 in set, GCD=6g=7no multiplesg=8no multiplesg=9no multiplesg=1010 in set, GCD=10Total achievable GCDs: 5 (g = 1, 2, 3, 6, 10)

g = 6 succeeds because 6 is in the array (GCD = 6). g = 7, 8, 9 have no multiples present. g = 10 succeeds because 10 is in the array (GCD = 10). Final count = 5.

Notice how the early-break optimization saves work. For g = 3, the algorithm finds 3 in the set immediately and stops, since GCD(3) = 3 = g.

Complexity analysis

ApproachTimeSpace
Brute force (all subsequences)O(2^n * n)O(n)
Candidate enumerationO(max_val * log(max_val))O(n)

The candidate enumeration approach iterates over every value g from 1 to max_val, and for each g it checks max_val / g multiples. The total number of multiple-checks across all candidates is max_val * (1 + 1/2 + 1/3 + ... + 1/max_val), which is the harmonic series summing to roughly max_val * ln(max_val). The space is O(n) for the set storing the original array elements.

Building blocks

GCD computation

The greatest common divisor of two integers can be computed in O(log(min(a, b))) time using the Euclidean algorithm. Python's math.gcd handles this efficiently, and the key property we rely on is that gcd(0, x) = x, which lets us initialize the running GCD to 0 and fold in elements one at a time.

Harmonic series enumeration

When you need to check all multiples of every integer from 1 to N, the total work is bounded by the harmonic series: N/1 + N/2 + N/3 + ... + N/N = N * H(N), where H(N) is approximately ln(N). This same pattern appears in the Sieve of Eratosthenes and many other number-theoretic algorithms.

Edge cases

  • Single element: If nums has just one element like [7], the only subsequence is [7] with GCD 7, so the answer is 1.
  • All elements identical: If nums = [5, 5, 5], every non-empty subsequence has GCD 5, so the answer is 1.
  • Consecutive integers: If nums = [1, 2, 3, ..., n], then every integer from 1 to n is achievable as a GCD, giving an answer of n.
  • Two coprime elements: If nums = [6, 35], the subsequences give GCDs 6, 35, and gcd(6, 35) = 1, so the answer is 3.

From understanding to recall

This problem combines two building blocks: GCD computation and harmonic series enumeration. The key insight, iterating over candidate values rather than over subsequences, is a pattern that appears whenever brute-forcing all subsets is too expensive but the answer space is bounded. Practicing this problem alongside sieve-based problems like Count Primes will reinforce the "enumerate multiples" technique. Revisiting it after a few days will help cement the connection between the harmonic series bound and the inner loop structure.

Try CodeBricks free

Related posts