Count subsequences with GCD equal to X

Approach

This problem can be solved using dynamic programming. We will apply the concept of dynamic programming in a bottom-up manner. In this approach, we will count the required subsequences till the index 'IND' and use it to find the answer for 'IND + 1'.

We will create a 2-dimensional 'DP[N][M]' array, where 'N' is the number of elements in the array 'ARR' and 'M' is the largest element in the array. 'DP[i][j]' denotes the number of subsequences with elements from arr[1. . .i] with gcd j.

To complete any dynamic programming solution, it is enough to mention the following three DP parameters:

Base Case:

'DP[0][0]' = 1. Since the number of subsequences with gcd 0 out of no elements is 1. This is kind of an assumption to facilitate the DP calculation.

Transition Statement:

We will iterate through the array, and for each index i, we have two obvious choices:

1. Take the current element: 'DP[i][gcd(j, ARR[i - 1])]' += 'DP[i - 1][j]'.
   
   
   • It is because to all the subsequences with gcd equal to gcd(j, ARR[i - 1]), we can add the current element 'ARR[i - 1]' to the subsequences with gcd equal to j.
      
2. Ignore the current element: 'DP[i][j]' += 'DP[i - 1][j]'.
   
   
   • The subsequences with gcd j that we can create with array elements till index i - 1 can also be created with array elements till index i.

Output

'DP[N][X]' represents the final answer to the problem.

It outputs the number of subsequences till 'ARR[1. . .N]', i.e. the whole array with gcd equal to 'X' input parameter.

Algorithm

1. Take the input parameters 'N', 'ARR' and 'X'.
2. Find the maximum element in the array 'ARR' and let it be 'MAX_ELEM'.
3. If the input parameter 'X' is greater than 'MAX_ELEM', the output is 0.
4. Create the 'DP' with size limits 'N' and 'MAX_ELEM'.
5. Run two nested for loops with limits 1 to 'N' and 0 to 'MAX_ELEM' with variables i and j, respectively.
6. For each possible value of the pair {i, j}, update the 'DP' array using the transition statements mentioned in the approach.
7. Output 'DP[N][X]'.

Program

// C++ program for the above approach
#include <iostream>
#include <climits>
#include <vector>
#include <algorithm>
using namespace std;


// Function to count the number of subsequences with the required gcd.
int countValidSubs(vector<int> &arr, int N, int X)
{
   // Maximum element in the array.
   int maxElem = *max_element(arr.begin(), arr.end());

   // GCD of two numbers is always less than the smaller of the two numbers.
   // It implies GCD of any subsequence will always be less than the maximum element in the array.
   // If 'X' is above the highest limit of the gcd, return 0.
   if (X > maxElem)
       return 0;

   // Create the dp table.
   vector<vector<int>> dp(N + 1, vector<int>(maxElem + 1));

   // Base Case as described in the approach.
   dp[0][0] = 1;

   // Iterate through all the indices.
   for (int i = 1; i <= N; i++)
   {
       // Consider all possible values of the gcd.
       for (int j = 0; j <= maxElem; j++)
       {
           // 1st Transition Statement - Consider the current array element.
           dp[i][__gcd(j, arr[i - 1])] += dp[i - 1][j];

           // 2nd Transition Statement - Ignore the current array element.
           dp[i][j] += dp[i - 1][j];

       }
   }

   // Return the answer dp[N][X].
   return dp[N][X];
}

int main()
{
   // Take the input parameters and array elements.
   int N;
   cout << "Enter the size of the array: ";
   cin >> N;
   vector<int> arr(N);
   cout << "Enter the elements: ";
   for (int i = 0; i < N; i++)
   {
       cin >> arr[i];
   }
   int X;
   cout << "Enter X: ";
   cin >> X;

   // Find the number of valid subsequences with gcd 'X'.
   int countSubs = countValidSubs(arr, N, X);

   // Output the answer.
   cout << countSubs << endl;

   return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input

Enter the size of the array: 5
Enter the elements: 2 3 6 8 10
Enter X: 2

Output

12

Time Complexity

The time complexity of the above approach is O(N * M), where 'N' is the size of the array and 'M' is the largest element in the array.

It is because we are running two nested loops with 'N' and 'M' as limits.

Space Complexity

The space complexity of the above approach is O(N * M), where 'N' is the size of the array and 'M' is the largest element in the array.

It is because we have created a 'DP' array with 'N' and 'M' as limits.

Key Takeaways

This blog discussed a coding challenge that can be solved with dynamic programming. The transition statement of a dynamic programming solution plays a vital role in its accuracy. Most of the time, the output and base case are evident if the DP strategy is clear. Many more standard problems can be solved with dynamic programming.

Hence learning never stops, and there is a lot more to learn.

Check out this problem - Longest Subarray With Sum K 

So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Coding!