Find the Number of Subsequences With Equal GCD

Find the Number of Subsequences With Equal GCD

1. What is this problem about?

The Find the Number of Subsequences With Equal GCD interview question is an advanced algorithmic challenge that combines number theory with combinatorial counting. You are given an array of integers and asked to find the number of pairs of non-empty, disjoint subsequences such that the Greatest Common Divisor (GCD) of the first subsequence is equal to the Greatest Common Divisor of the second subsequence. This problem requires a deep understanding of how GCD behaves across different sets of numbers and how to count these occurrences efficiently.

2. Why is this asked in interviews?

Companies like Infosys ask the Find the Number of Subsequences With Equal GCD coding problem to evaluate a candidate's ability to handle complex state transitions and optimization techniques. It tests your proficiency in Dynamic Programming and Number Theory. The problem is particularly effective at identifying candidates who can move beyond basic brute force and leverage mathematical properties (like the limited range of GCD values) to design an efficient solution.

3. Algorithmic pattern used

This problem is best solved using the Dynamic Programming interview pattern.

• State Definition: A 2D DP table dp[g1][g2] can represent the number of ways to form two disjoint subsequences with GCDs g1 and g2.
• Transitions: For each new number x in the array, you have three choices:
  1. Add x to the first subsequence: New GCD is gcd(g1, x).
  2. Add x to the second subsequence: New GCD is gcd(g2, x).
  3. Don't include x in either.
• Optimization: Since the maximum value of a GCD is limited by the maximum value in the array (often up to 200 or 1000), the state space is manageable.

4. Example explanation

Suppose the array is [2, 2, 4].

• One pair could be: Subsequence 1: [2], Subsequence 2: [4]. GCDs: gcd(2)=2, gcd(4)=4. Not equal.
• Another pair: Subsequence 1: [2], Subsequence 2: [2]. GCDs: gcd(2)=2, gcd(2)=2. Equal!
• Another: Subsequence 1: [2], Subsequence 2: [4, 2]. GCDs: gcd(2)=2, gcd(4, 2)=2. Equal! The algorithm counts all such valid disjoint pairs.

5. Common mistakes candidates make

• Brute Force: Trying to generate all $3^N$ possible ways to assign elements to two subsequences or none. This is computationally impossible for $N > 20$.
• Ignoring Disjointness: Failing to ensure that an element used in the first subsequence is not used in the second.
• Modulo Errors: Forgetting to apply the modulo operation at each addition step in the DP, leading to integer overflows.

6. Interview preparation tip

Master the properties of GCD. Remember that $gcd(a, b) \leq min(a, b)$ and that adding a number to a set can only decrease or maintain the GCD. This "monotonic" property is what makes GCD-based DP problems solvable within restricted value ranges.