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.
[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.
[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 <= 1051 <= nums[i] <= 2 * 105Problem Overview: Given an integer array nums, count how many distinct values can appear as the GCD of some non‑empty subsequence. You do not need to generate subsequences explicitly. The goal is to determine how many integers g exist such that some subset of numbers in nums has gcd = g.
Approach 1: Direct Counting of GCD Divisors (O(M log M) time, O(M) space)
This approach leverages the mathematical structure of GCDs. Instead of enumerating subsequences, iterate candidate GCD values from 1 to max(nums). For each candidate g, check all multiples of g that appear in the array. Maintain a running GCD of these multiples using the Euclidean algorithm. If the accumulated GCD becomes exactly g, then there exists a subsequence whose GCD is g. A boolean presence array or hash set allows O(1) membership checks for multiples. This transforms the exponential subsequence search into a number‑theory iteration over multiples. The runtime is roughly proportional to the harmonic series over multiples, giving O(M log M) time where M = max(nums), and O(M) extra space. This method relies heavily on concepts from number theory and efficient gcd computation.
Approach 2: Efficient Multiple Checking Using Direct Subsequence Logic (O(M log M) time, O(M) space)
This strategy focuses on checking whether a target value can be formed as the GCD of some subsequence by examining its multiples. Store all array values in a fast lookup structure such as a boolean array. For each potential GCD x, iterate through multiples x, 2x, 3x... up to max(nums). If a multiple exists in the array, merge it into a running GCD calculation. The moment the running value equals x, you know a subsequence can produce that GCD, so you increment the answer and stop scanning further multiples. The key insight: if the GCD of several multiples equals x, some subsequence among them must produce that value. This approach avoids generating combinations entirely and turns the problem into structured iteration over multiples. The technique is common in math-driven array problems and uses simple presence checks over the array.
Recommended for interviews: Interviewers typically expect the multiple‑checking GCD approach. A brute subsequence enumeration quickly becomes infeasible because the number of subsequences is 2^n. Demonstrating the insight that every valid GCD must divide at least one array element shows strong algorithmic thinking and familiarity with number theory optimizations. The optimal solution runs in near linear time relative to the maximum value in the array, which is the key observation interviewers look for.
For each possible GCD value starting from 1, we check if it is a GCD of any subsequence by iterating through its multiples in the array. If we find at least two different multiples, we confirm its status as a potential subsequence GCD and increase our count.
This Python solution initializes a counter for GCDs. For each potential GCD x starting from 1, it checks its multiples in nums. Using the math.gcd function, if a valid GCD is confirmed, it increments the count.
Time Complexity: O(n log(max)), where n is the number of unique numbers in nums and max is 200,000. Space Complexity: O(n) to store nums as a set.
This approach optimizes checking by directly verifying each integer from 1 to the maximum possible value, and counting how often it can be a GCD by checking direct multiples. It uses presence flags and sub-groups to efficiently cover the possibility of GCD formation over direct range checks.
The Java solution uses an efficient boolean array to track the presence of each integer. It employs a direct check for possible GCD formation by evaluating multiples and updating the count if conditions are met, using a helper method for GCD calculation.
Java
JavaScript
Time Complexity: O(n log(max)). Space Complexity: O(max) for the boolean presence array.
For all sub-sequences of the array nums, their greatest common divisor (GCD) will not exceed the maximum value mx in the array.
Therefore, we can enumerate each number x in [1,.. mx], and determine whether x is the GCD of a sub-sequence of the array nums. If it is, then we increment the answer by one.
So the problem is transformed into: determining whether x is the GCD of a sub-sequence of the array nums. We can do this by enumerating the multiples y of x, and checking whether y exists in the array nums. If y exists in the array nums, then we calculate the GCD g of y. If g = x occurs, then x is the GCD of a sub-sequence of the array nums.
The time complexity is O(n + M times log M), and the space complexity is O(M). Here, n and M are the length of the array nums and the maximum value in the array nums, respectively.
| Approach | Complexity |
|---|---|
| Direct Counting of GCD Divisors | Time Complexity: O(n log(max)), where n is the number of unique numbers in nums and max is 200,000. Space Complexity: O(n) to store nums as a set. |
| Efficient Multiple Checking Using Direct Subsequence | Time Complexity: O(n log(max)). Space Complexity: O(max) for the boolean presence array. |
| Enumeration + Mathematics | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Counting of GCD Divisors | O(M log M) | O(M) | General case when max value is manageable and you want a clean number‑theory approach |
| Efficient Multiple Checking Using Direct Subsequence | O(M log M) | O(M) | Interview‑preferred approach; avoids subsequence generation and uses GCD accumulation |
1819. Number of Different Subsequences GCDs | LEETCODE WEEKLY CONTEST 235 | LEETCODE HARD • code Explainer • 2,051 views views
Watch 9 more video solutions →Practice Number of Different Subsequences GCDs with our built-in code editor and test cases.
Practice on FleetCode