Skip to main content
Talentd

Number of Different Subsequences GCDs - Solution & Explanation

HardArrayMathCountingNumber Theory11 min readAsked at: Infosys, Akuna Capital
Practice this problem

Problem Statement

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

Approach Overview

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

Approach 1: Direct Counting of GCD Divisors

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.

Code

PythonC++

Python

C++

Complexity

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.

Try this approach in the editor →

Approach 2: Efficient Multiple Checking Using Direct Subsequence

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.

Code

JavaJavaScript

Java

JavaScript

Complexity

Time Complexity: O(n log(max)). Space Complexity: O(max) for the boolean presence array.

Try this approach in the editor →

Approach 3: Enumeration + Mathematics

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.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct Counting of GCD DivisorsO(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 SubsequenceO(M log M)O(M)Interview‑preferred approach; avoids subsequence generation and uses GCD accumulation

Video Solution

1819. Number of Different Subsequences GCDs | LEETCODE WEEKLY CONTEST 235 | LEETCODE HARD • code Explainer • 2,128 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Number of Different Subsequences GCDs easy or hard?
The problem is rated Hard because the straightforward subsequence interpretation leads to exponential thinking. The correct solution requires recognizing a number‑theory pattern and iterating over divisors and multiples efficiently.
Number of Different Subsequences GCDs Python/Java solution
Python, Java, C++, and JavaScript implementations typically follow the same pattern: build a presence array, iterate candidate GCD values, scan their multiples, and maintain a running GCD using the Euclidean algorithm. The logic stays identical across languages.
How to solve Number of Different Subsequences GCDs in O(n)?
A strict O(n) solution is not typical because the algorithm depends on scanning multiples up to the maximum value in the array. The practical optimal solution is O(M log M), where M = max(nums). It uses a presence array and repeatedly computes GCDs of multiples to verify whether a candidate value can be formed.
What is the best approach for Number of Different Subsequences GCDs?
The most effective approach iterates over every possible GCD value from 1 to max(nums) and checks its multiples in the array. By computing the running GCD of these multiples, you can determine whether a subsequence exists with that exact GCD. This avoids generating subsequences and runs in about O(M log M) time where M is the maximum number in the array.
Is Number of Different Subsequences GCDs asked at Google/Amazon/Meta?
Problems involving GCD properties, divisor iteration, and number‑theory optimizations frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that require reasoning about divisibility and efficient enumeration of factors are especially common in senior algorithm rounds.
What data structure is used in Number of Different Subsequences GCDs?
Most implementations use a boolean array or hash set to record which numbers appear in the input. This allows constant‑time membership checks while iterating through multiples of candidate GCD values.
What is the time complexity of Number of Different Subsequences GCDs?
The optimal solution runs in O(M log M) time where M is the maximum value in the array. For each candidate GCD, the algorithm scans its multiples and performs constant‑time presence checks plus fast Euclidean GCD operations.

Ready to solve this problem?

Practice Number of Different Subsequences GCDs with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Greatest Common Divisor of Array