1.
Understanding
2.
Problem Statement
2.1.
Input
2.2.
Output
2.3.
Explanation
2.4.
Input
2.5.
Output
2.6.
Explanation
3.
Approach
3.1.
Algorithm
3.2.
Program
3.3.
Input
3.4.
Output
3.5.
Time Complexity
3.6.
Space Complexity
4.
Key Takeaways
Last Updated: Mar 27, 2024

Count subsequences with GCD equal to X

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Understanding

This blog discusses a problem based on dynamic programming. Dynamic programming is one of the most asked concepts in programming contests and technical interviews. Dynamic Programming divides a problem into identical subproblems and solves each part to reach the final answer. In this blog, we will discuss the application of this concept in one such coding problem.

Problem Statement

Ninja has given you an array 'ARR' and an integer 'X'. Your task is to determine the number of subsequences of array elements with the Greatest Common Divisor (GCD) equal to 'X'.

Input

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

Output

``12``

Explanation

The required subsequences are {2}, {2, 6}, {2, 8}, {2, 10} {2, 6, 8}, {2, 6, 8, 10}, {2, 8, 10}, {2, 6, 10} {6, 8}, {6, 8, 10}, {6, 10}, {8, 10}.

Input

``````Enter the size of the array: 4
Enter the elements: 2 4 6 8
Enter X: 3``````

Output

``0``

Explanation

No subsequence satisfies the criteria.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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 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);

cout << countSubs << endl;

return 0;
}``````

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!

Live masterclass