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.

Description Hints 1 Solution Video 40:13

3336. Find the Number of Subsequences With Equal GCD

Hard66.7% acceptance2 companies

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 10⁹ + 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

Asked at 2 companies

Infosys

Google

Topics

Hints open one at a time

Hint 1

Use dynamic programming to store number of subsequences up till index i with GCD g1 and g2.

40:13

Still stuck?Read 2 approaches, or watch a walkthrough.

Open solution