Skip to main content
Talentd

Find the Number of Subsequences With Equal GCD - Solution & Explanation

HardArrayMathDynamic ProgrammingNumber Theory6 min readAsked at: Infosys, Google
Practice this problem

Problem Statement

You are given an integer array nums.

Your task is to find the number of pairs of non-empty subsequences (seq1, seq2) of nums that satisfy the following conditions:

  • The subsequences seq1 and seq2 are disjoint, meaning no index of nums is common between them.
  • The GCD of the elements of seq1 is equal to the GCD of the elements of seq2.

Return the total number of such pairs.

Since the answer may be very large, return it modulo 109 + 7.

 

Example 1:

Input: nums = [1,2,3,4]

Output: 10

Explanation:

The subsequence pairs which have the GCD of their elements equal to 1 are:

  • ([1, 2, 3, 4], [1, 2, 3, 4])
  • ([1, 2, 3, 4], [1, 2, 3, 4])
  • ([1, 2, 3, 4], [1, 2, 3, 4])
  • ([1, 2, 3, 4], [1, 2, 3, 4])
  • ([1, 2, 3, 4], [1, 2, 3, 4])
  • ([1, 2, 3, 4], [1, 2, 3, 4])
  • ([1, 2, 3, 4], [1, 2, 3, 4])
  • ([1, 2, 3, 4], [1, 2, 3, 4])
  • ([1, 2, 3, 4], [1, 2, 3, 4])
  • ([1, 2, 3, 4], [1, 2, 3, 4])

Example 2:

Input: nums = [10,20,30]

Output: 2

Explanation:

The subsequence pairs which have the GCD of their elements equal to 10 are:

  • ([10, 20, 30], [10, 20, 30])
  • ([10, 20, 30], [10, 20, 30])

Example 3:

Input: nums = [1,1,1,1]

Output: 50

 

Constraints:

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 200

Approach Overview

Problem Overview: Given an integer array, count how many pairs of non‑empty subsequences produce the same greatest common divisor (GCD). The challenge is that the number of subsequences grows exponentially, so you cannot enumerate them directly. The goal is to track GCD values formed by subsequences and combine counts efficiently.

Approach 1: Efficient Counting with GCD Tracking (O(n * M log M) time, O(M) space)

Track how many subsequences produce each possible GCD while iterating through the array. For each number x, extend previously formed subsequences by computing gcd(prev_gcd, x). Maintain a frequency map where the key is the GCD value and the value is the number of subsequences producing that GCD. This works because the GCD of a subsequence can be updated incrementally. Once counts for each GCD are known, compute how many pairs of subsequences share the same GCD using combinatorics (for example count * (count - 1) / 2). The repeated gcd operations are fast, so the overall complexity stays manageable. This technique relies heavily on properties of number theory and incremental aggregation.

Approach 2: Dynamic Programming for GCD Subsequences (O(n * M^2 log M) time, O(M^2) space)

Model the problem with dynamic programming where the state represents the GCD values of two subsequences being built simultaneously. When processing each element, decide whether to add it to the first subsequence, the second subsequence, or skip it. Update the state using gcd(current_gcd, nums[i]). This creates a transition graph over possible GCD pairs. At the end, sum the states where both subsequences have the same non-zero GCD. The approach is more explicit and easier to reason about, but the state space grows with the maximum value in the array. This technique demonstrates classic dynamic programming over subsequence construction combined with repeated math operations.

Recommended for interviews: The GCD tracking approach is the one most interviewers expect. It shows you understand how subsequence GCDs evolve and how to compress exponential possibilities into aggregated counts. The DP formulation demonstrates correctness but is heavier in both time and memory.

Approach 1: Efficient Counting with GCD Tracking

This approach involves efficiently keeping track of potential GCDs by iterating through all possible numbers. We calculate the number of subsequences for each possible GCD and use combinatorial principles to find disjoint subsequences.

In this Python solution, we iterate over every possible GCD value and calculate the number of subsequences that could result in each GCD. We calculate powers of 2 to get all possible non-empty subsequences and compute the result for disjoint pairs.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(n * log(max_num)) where n is the number of elements in the input.
Space Complexity: O(max_num)

Try this approach in the editor →

Approach 2: Dynamic Programming for GCD Subsequences

This approach leverages dynamic programming. We maintain a dp table where dp[i][g] represents the number of subsequences ending at index i with GCD g. This method incrementally builds up the solution using possible divisors.

In this Java solution, we use recursion with memoization to explore different possible subsequences that share the same GCD. The function 'pow' is used to compute the power mod iteratively to prevent overflow.

Code

Java

Java

Complexity

Time Complexity: O(n * log(max_num))
Space Complexity: O(max_num)

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Efficient Counting with GCD Tracking

Time Complexity: O(n * log(max_num)) where n is the number of elements in the input.
Space Complexity: O(max_num)

Dynamic Programming for GCD Subsequences

Time Complexity: O(n * log(max_num))
Space Complexity: O(max_num)

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Efficient Counting with GCD TrackingO(n * M log M)O(M)General case and large arrays where subsequences cannot be enumerated
Dynamic Programming for GCD SubsequencesO(n * M^2 log M)O(M^2)When explicitly modeling two subsequences and reasoning about transitions

Video Solution

Find the Number of Subsequences With Equal GCD | Detailed Explanation | 3 Ways | Leetcode 3336 | MIK • codestorywithMIK • 9,372 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find the Number of Subsequences With Equal GCD easy or hard?
Find the Number of Subsequences With Equal GCD is classified as a Hard problem. The difficulty comes from combining subsequence enumeration, gcd properties, and dynamic programming state compression to avoid exponential complexity.
Find the Number of Subsequences With Equal GCD Python/Java solution
Python and C++ implementations usually use a dictionary or unordered_map to track GCD counts and update them incrementally for each number. Java solutions often use dynamic programming tables or maps to represent GCD states and transitions. All implementations rely on repeated gcd computations and aggregated counting.
How to solve Find the Number of Subsequences With Equal GCD in O(n)?
A strict O(n) solution is generally not feasible because multiple GCD states must be maintained. The practical optimal approach is O(n * M log M), where each array element updates previously seen GCD states using the gcd operation. The state space is limited by the number of possible GCD values.
What is the best approach for Find the Number of Subsequences With Equal GCD?
The most efficient approach tracks counts of subsequences by their GCD values while iterating through the array. Each new element updates existing GCD states using gcd(prev_gcd, value). After computing counts for every possible GCD, pairs of subsequences with the same GCD are counted using combinatorics. This runs in about O(n * M log M) time where M is the maximum array value.
Is Find the Number of Subsequences With Equal GCD asked at Google/Amazon/Meta?
Problems involving subsequence GCD counting, dynamic programming on number properties, and gcd aggregation appear in interviews at companies like Google, Amazon, and Meta. Variants that combine number theory with dynamic programming are especially common in senior or hard-level interview rounds.
What data structure is used in Find the Number of Subsequences With Equal GCD?
Most efficient implementations use a hash map or array to store counts of subsequences grouped by their current GCD value. The algorithm repeatedly updates these counts using the gcd function while iterating through the array, which compresses exponentially many subsequences into manageable states.
What is the time complexity of Find the Number of Subsequences With Equal GCD?
The optimized solution runs in O(n * M log M) time with O(M) space by maintaining counts of subsequences grouped by their GCD values. A more explicit dynamic programming formulation that tracks two subsequences simultaneously can take O(n * M^2 log M) time and O(M^2) space.

Ready to solve this problem?

Practice Find the Number of Subsequences With Equal GCD with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Greatest Common Divisor of Array