LeetCode 1819 - Number of Different Subsequences GCDs

Difficulty: 🔴 Hard
Topics: Array, Math, Counting, Number Theory

Solution

Problem Understanding

The problem asks us to compute how many distinct values can appear as the GCD of some non-empty subsequence of the given array.

A subsequence is formed by deleting zero or more elements while preserving order. Since the order does not matter for the GCD operation, the real challenge is determining which integers can be produced as the GCD of some subset of values.

For example, if nums = [6,10,3], the possible subsequences include:

[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 = 1

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

The constraints are extremely important:

nums.length <= 10^5
nums[i] <= 2 * 10^5

A brute-force enumeration of all subsequences is impossible because an array of size 10^5 has 2^100000 subsequences.

The maximum value is only 2 * 10^5, which strongly suggests that the solution should focus on values and divisibility properties rather than on subsequences directly. This is a classic number theory optimization pattern.

Several edge cases are important:

Arrays containing only one number
Arrays with many duplicates
Arrays where all numbers are coprime
Arrays where all numbers are multiples of one base value
Arrays containing 1, because once 1 exists, it is automatically a valid subsequence GCD

The problem guarantees that all numbers are positive integers, so we never need to handle zero or negative values in GCD computations.

Approaches

Brute Force Approach

The most direct approach is to generate every non-empty subsequence, compute its GCD, and insert the result into a set.

For each subsequence:

Build the subsequence
Compute the GCD of all elements in it
Store the GCD in a hash set

At the end, the size of the set is the answer.

This works because every subsequence is examined exactly once, so every possible subsequence GCD will eventually be inserted into the set.

However, this approach is completely infeasible. An array with n elements has 2^n - 1 non-empty subsequences. Even for n = 30, this becomes enormous. With n = 10^5, it is impossible.

Key Insight

Instead of generating subsequences, we reverse the thinking.

Suppose we want to know whether some integer g can be the GCD of a subsequence.

If g is the GCD of some subsequence, then every number in that subsequence must be divisible by g.

Therefore, we only need to look at numbers in the array that are multiples of g.

Now consider all numbers in nums that are divisible by g. If the GCD of all such numbers equals g, then some subsequence can achieve GCD g.

Why?

Because repeatedly taking GCDs can only decrease or stay the same. If the overall GCD of all multiples of g becomes exactly g, then there exists a subset whose GCD is g.

This transforms the problem into:

For every possible integer g from 1 to max(nums):

Collect all array values divisible by g
Compute their GCD
If the result equals g, count it

This avoids subsequence generation entirely.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n × n)	O(number of distinct GCDs)	Enumerates every subsequence
Optimal	O(M log M) approximately	O(M)	Uses divisibility and GCD properties

Here, M = max(nums).

Algorithm Walkthrough

Step 1: Store all numbers for fast lookup

We first create a boolean array or set indicating which numbers exist in nums.

This allows us to quickly check whether a particular multiple exists in the array.

For example:

nums = [6,10,3]
present[3] = true
present[6] = true
present[10] = true

This is important because later we will iterate through multiples of candidate GCD values.

Step 2: Iterate through every possible GCD candidate

We try every integer g from 1 to max(nums).

The question becomes:

"Can g appear as the GCD of some subsequence?"

Step 3: Examine all multiples of `g`

If g is a subsequence GCD, then every element in that subsequence must be divisible by g.

So we iterate through:

g, 2g, 3g, 4g, ...

up to max(nums).

For each multiple that actually exists in the array, we include it in a running GCD computation.

Step 4: Compute the running GCD

Suppose g = 2.

We examine all numbers in the array divisible by 2.

If the running GCD of those numbers eventually becomes 2, then 2 is achievable.

Example:

nums = [6,10,3]

Multiples of 2 present:
6, 10

gcd(6,10) = 2

So 2 is a valid subsequence GCD.

Step 5: Count valid GCDs

Whenever the running GCD becomes exactly equal to g, we increment the answer.

At that point we can stop early for that g, because additional numbers cannot increase the GCD again.

Why it works

The algorithm relies on a key number theory property:

If some subsequence has GCD g, then every element of that subsequence must be divisible by g.

Therefore, the subsequence must be drawn entirely from the set of array elements that are multiples of g.

Now consider the GCD of all such multiples present in the array. If this overall GCD equals g, then there exists a subset whose GCD is exactly g. Conversely, if the GCD remains larger than g, then every possible subsequence formed from those multiples must also have GCD larger than g.

Thus, checking the GCD of all present multiples correctly determines whether g can appear as a subsequence GCD.

Python Solution

from typing import List
from math import gcd

class Solution:
    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:
        max_num = max(nums)

        present = [False] * (max_num + 1)

        for num in nums:
            present[num] = True

        answer = 0

        for candidate_gcd in range(1, max_num + 1):
            current_gcd = 0

            for multiple in range(candidate_gcd, max_num + 1, candidate_gcd):
                if present[multiple]:
                    current_gcd = gcd(current_gcd, multiple)

                    if current_gcd == candidate_gcd:
                        answer += 1
                        break

        return answer

The implementation begins by finding the maximum value in the array because this determines the upper bound of all possible GCD values.

We then build the present array, which acts like a frequency or existence table. This allows constant time checks for whether a number exists in the input.

Next, we iterate through every possible candidate GCD from 1 to max_num.

For each candidate:

We initialize current_gcd to 0
We iterate through all multiples of the candidate
If a multiple exists in the array, we update the running GCD

The mathematical property:

gcd(0, x) = x

makes initialization simple.

As soon as the running GCD becomes equal to the candidate, we know this candidate is achievable, so we increment the answer and stop processing further multiples.

The early break is an important optimization because once the GCD reaches the candidate value, adding more numbers cannot increase it again.

Go Solution

package main

func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

func countDifferentSubsequenceGCDs(nums []int) int {
	maxNum := 0

	for _, num := range nums {
		if num > maxNum {
			maxNum = num
		}
	}

	present := make([]bool, maxNum+1)

	for _, num := range nums {
		present[num] = true
	}

	answer := 0

	for candidateGCD := 1; candidateGCD <= maxNum; candidateGCD++ {
		currentGCD := 0

		for multiple := candidateGCD; multiple <= maxNum; multiple += candidateGCD {
			if present[multiple] {
				currentGCD = gcd(currentGCD, multiple)

				if currentGCD == candidateGCD {
					answer++
					break
				}
			}
		}
	}

	return answer
}

The Go implementation follows the same logic as the Python version.

One notable difference is that Go does not provide a built-in GCD function in the standard library for integers, so we implement Euclid's algorithm manually.

The present slice is allocated with size maxNum + 1 so indices map directly to values.

Go slices are automatically initialized to false, which works naturally for the existence table.

Integer overflow is not a concern because all values remain within the problem constraints.

Worked Examples

Example 1

nums = [6,10,3]

Maximum value:

max_num = 10

Present array contains:

3, 6, 10

Now test each candidate GCD.

Candidate GCD	Multiples Present	Running GCD	Valid?
1	3, 6, 10	gcd(3,6,10)=1	Yes
2	6, 10	gcd(6,10)=2	Yes
3	3, 6	gcd(3,6)=3	Yes
4	none	no computation	No
5	10	gcd(10)=10	No
6	6	gcd(6)=6	Yes
7	none	no computation	No
8	none	no computation	No
9	none	no computation	No
10	10	gcd(10)=10	Yes

Total valid GCDs:

1, 2, 3, 6, 10

Answer:

Example 2

nums = [5,15,40,5,6]

Present values:

5, 6, 15, 40

Now evaluate candidates.

Candidate GCD	Multiples Present	Final GCD	Valid?
1	5,6,15,40	1	Yes
2	6,40	2	Yes
3	6,15	3	Yes
4	40	40	No
5	5,15,40	5	Yes
6	6	6	Yes
10	40	40	No
15	15	15	Yes
40	40	40	Yes

Distinct achievable GCDs:

1,2,3,5,6,15,40

Answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(M log M) approximately	Harmonic series over multiples plus GCD operations
Space	O(M)	Presence table

Let M = max(nums).

For each candidate g, we iterate through its multiples:

M/g

So the total iterations become:

M/1 + M/2 + M/3 + ... + M/M

This is:

M × (1 + 1/2 + 1/3 + ...)

which evaluates to approximately:

O(M log M)

Each iteration performs a GCD computation, which is very fast in practice because Euclid's algorithm runs in logarithmic time relative to the values involved.

The space complexity is dominated by the boolean presence array.

Test Cases

from typing import List

class Solution:
    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:
        from math import gcd

        max_num = max(nums)

        present = [False] * (max_num + 1)

        for num in nums:
            present[num] = True

        answer = 0

        for candidate_gcd in range(1, max_num + 1):
            current_gcd = 0

            for multiple in range(candidate_gcd, max_num + 1, candidate_gcd):
                if present[multiple]:
                    current_gcd = gcd(current_gcd, multiple)

                    if current_gcd == candidate_gcd:
                        answer += 1
                        break

        return answer

sol = Solution()

assert sol.countDifferentSubsequenceGCDs([6, 10, 3]) == 5
# basic example from problem statement

assert sol.countDifferentSubsequenceGCDs([5, 15, 40, 5, 6]) == 7
# second official example

assert sol.countDifferentSubsequenceGCDs([1]) == 1
# smallest possible input

assert sol.countDifferentSubsequenceGCDs([7]) == 1
# single non-one value

assert sol.countDifferentSubsequenceGCDs([2, 4, 6, 8]) == 4
# produces gcds 2,4,6,8

assert sol.countDifferentSubsequenceGCDs([3, 6, 9]) == 3
# gcds are 3,6,9

assert sol.countDifferentSubsequenceGCDs([2, 3, 5, 7]) == 5
# primes plus gcd 1

assert sol.countDifferentSubsequenceGCDs([5, 5, 5, 5]) == 1
# duplicate values only

assert sol.countDifferentSubsequenceGCDs([2, 4, 8, 16]) == 4
# powers of two

assert sol.countDifferentSubsequenceGCDs([6, 12, 18, 24]) == 5
# gcds include 6,12,18,24, and 2

Test	Why
`[6,10,3]`	Validates official example
`[5,15,40,5,6]`	Tests duplicates and mixed divisibility
`[1]`	Smallest valid input
`[7]`	Single element non-one case
`[2,4,6,8]`	Multiple even divisibility relationships
`[3,6,9]`	Shared common factor
`[2,3,5,7]`	Pairwise coprime numbers
`[5,5,5,5]`	Heavy duplication
`[2,4,8,16]`	Powers of a single base
`[6,12,18,24]`	Multiple shared factors

Edge Cases

Arrays containing only one element

A single-element array is important because the only possible subsequence is the element itself.

For example:

nums = [7]

The only subsequence GCD is 7.

A buggy implementation might incorrectly assume smaller divisors like 1 are also achievable. Our implementation avoids this because it only validates a candidate if the running GCD of present multiples becomes exactly equal to that candidate.

Arrays with many duplicates

Consider:

nums = [5,5,5,5]

Even though there are many subsequences, every non-empty subsequence has GCD 5.

The correct answer is 1.

Our implementation handles duplicates naturally because the presence table only tracks whether a value exists, not how many times it appears. Duplicate copies do not change the GCD computation.

Arrays containing pairwise coprime numbers

Consider:

nums = [2,3,5,7]

Each individual number is a valid GCD, and combining different primes produces GCD 1.

The distinct GCDs are:

1,2,3,5,7

This case is important because it ensures the algorithm correctly discovers 1 through repeated GCD reduction across multiple values.

Arrays where no smaller divisor is achievable

Consider:

nums = [4,8,16]

Although all numbers are divisible by 2, no subsequence has GCD 2.

The GCDs are:

4,8,16

Our algorithm correctly rejects 2 because:

gcd(4,8,16) = 4

which never becomes 2.

This demonstrates why checking divisibility alone is insufficient, we must compute the actual GCD of the multiples.

LeetCode 1819 - Number of Different Subsequences GCDs

Solution

Problem Understanding

Approaches

Brute Force Approach

Key Insight

Approach Comparison

Algorithm Walkthrough

Step 1: Store all numbers for fast lookup

Step 2: Iterate through every possible GCD candidate

Step 3: Examine all multiples of g

Step 4: Compute the running GCD

Step 5: Count valid GCDs

Why it works

Python Solution

Go Solution

Worked Examples

Example 1

Example 2

Complexity Analysis

Test Cases

Edge Cases

Arrays containing only one element

Arrays with many duplicates

Arrays containing pairwise coprime numbers

Arrays where no smaller divisor is achievable

Step 3: Examine all multiples of `g`