Given an array a of size N. The task is to find a subsequence X of length K such that gcd(X[0], X[1]) + (X[2], X[3]) + … is maximum.
Note: K is even.
Examples:
Input: a[] = {4, 5, 3, 7, 8, 10, 9, 8}, k = 4
Output: 9
The subsequence {4, 7, 8, 8} gives the maximum value = 9.
Other subsequences like { 5, 3, 8, 8} also gives 9.
Input: a[] = {5, 8, 16, 20}, K = 2
Output:
The subsequence {8, 16} gives the maximum value.
Naive Approach: A naive approach is to generate all subsequences of length K using recursion and find the maximum value possible.
Efficient Approach: An efficient approach is to use Dynamic Programming to solve the above problem. Let dp[i][j] denote the value of the pair gcd sum if i-th index element is taken as the j-th element. Recursively generate all subsequences possible. If cnt of elements taken is odd then add gcd(a[prev], a[current]) to the sum since this number will be the second in the pair and recur for next element. If cnt is even, then simply recur setting a[i] as the previous element. Memoization has been used to avoid re-calculation of the same recurrence. The maximum of all the generated sums will be the answer.
Below is the implementation of the above approach:
C++
// C++ program to find the sum of // the addition of all possible subsets #include <bits/stdc++.h> using namespace std; const int MAX = 100; // Recursive function to find the maximum value of // the given recurrence int recur( int ind, int cnt, int last, int a[], int n, int k, int dp[][MAX]) { // If we get K elements if (cnt == k) return 0; // If we have reached the end // and K elements are not there if (ind == n) return -1e9; // If the state has been visited if (dp[ind][cnt] != -1) return dp[ind][cnt]; int ans = 0; // Iterate for every element as the // next possible element // and take the element which gives // the maximum answer for ( int i = ind; i < n; i++) { // If this element is the first element // in the individual pair in the subsequence // then simply recurrence with the last // element as i-th index if (cnt % 2 == 0) ans=max(ans,recur(i + 1, cnt + 1, i, a, n, k, dp)); // If this element is the second element in // the individual pair, the find gcd with // the previous element and add to the answer // and recur for the next element else ans = max(ans, __gcd(a[last], a[i]) + recur(i + 1, cnt + 1, 0, a, n, k, dp)); } return dp[ind][cnt] = ans; } // Driver Code int main() { int a[] = { 4, 5, 3, 7, 8, 10, 9, 8 }; int n = sizeof (a) / sizeof (a[0]); int k = 4; int dp[n][MAX]; memset (dp, -1, sizeof dp); cout << recur(0, 0, 0, a, n, k, dp); } |
Java
// Java program to find the sum of // the addition of all possible subsets import java.util.*; class GFG { static int MAX = 100 ; // Recursive function to find the maximum value of // the given recurrence static int recur( int ind, int cnt, int last, int a[], int n, int k, int dp[][]) { // If we get K elements if (cnt == k) return 0 ; // If we have reached the end // and K elements are not there if (ind == n) return ( int ) -1e9; // If the state has been visited if (dp[ind][cnt] != - 1 ) return dp[ind][cnt]; int ans = 0 ; // Iterate for every element as the // next possible element // and take the element which gives // the maximum answer for ( int i = ind; i < n; i++) { // If this element is the first element // in the individual pair in the subsequence // then simply recurrence with the last // element as i-th index if (cnt % 2 == 0 ) ans = Math.max(ans,recur(i + 1 , cnt + 1 , i, a, n, k, dp)); // If this element is the second element in // the individual pair, the find gcd with // the previous element and add to the answer // and recur for the next element else ans = Math.max(ans, __gcd(a[last], a[i]) + recur(i + 1 , cnt + 1 , 0 , a, n, k, dp)); } return dp[ind][cnt] = ans; } static int __gcd( int a, int b) { if (b == 0 ) return a; return __gcd(b, a % b); } // Driver Code public static void main(String[] args) { int a[] = { 4 , 5 , 3 , 7 , 8 , 10 , 9 , 8 }; int n = a.length; int k = 4 ; int [][]dp = new int [n][MAX]; for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j < MAX; j++) { dp[i][j] = - 1 ; } } System.out.println(recur( 0 , 0 , 0 , a, n, k, dp)); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program to find the sum of # the addition of all possible subsets from math import gcd as __gcd MAX = 100 # Recursive function to find the # maximum value of the given recurrence def recur(ind, cnt, last, a, n, k, dp): # If we get K elements if (cnt = = k): return 0 # If we have reached the end # and K elements are not there if (ind = = n): return - 10 * * 9 # If the state has been visited if (dp[ind][cnt] ! = - 1 ): return dp[ind][cnt] ans = 0 # Iterate for every element as the # next possible element # and take the element which gives # the maximum answer for i in range (ind, n): # If this element is the first element # in the individual pair in the subsequence # then simply recurrence with the last # element as i-th index if (cnt % 2 = = 0 ): ans = max (ans, recur(i + 1 , cnt + 1 , i, a, n, k, dp)) # If this element is the second element in # the individual pair, the find gcd with # the previous element and add to the answer # and recur for the next element else : ans = max (ans, __gcd(a[last], a[i]) + recur(i + 1 , cnt + 1 , 0 , a, n, k, dp)) dp[ind][cnt] = ans return ans # Driver Code a = [ 4 , 5 , 3 , 7 , 8 , 10 , 9 , 8 ] n = len (a) k = 4 ; dp = [[ - 1 for i in range ( MAX )] for i in range (n)] print (recur( 0 , 0 , 0 , a, n, k, dp)) # This code is contributed by Mohit Kumar |
C#
// C# program to find the sum of // the addition of all possible subsets using System; class GFG { static int MAX = 100; // Recursive function to find the maximum value of // the given recurrence static int recur( int ind, int cnt, int last, int []a, int n, int k, int [,]dp) { // If we get K elements if (cnt == k) return 0; // If we have reached the end // and K elements are not there if (ind == n) return ( int ) -1e9; // If the state has been visited if (dp[ind,cnt] != -1) return dp[ind,cnt]; int ans = 0; // Iterate for every element as the // next possible element // and take the element which gives // the maximum answer for ( int i = ind; i < n; i++) { // If this element is the first element // in the individual pair in the subsequence // then simply recurrence with the last // element as i-th index if (cnt % 2 == 0) ans = Math.Max(ans,recur(i + 1, cnt + 1, i, a, n, k, dp)); // If this element is the second element in // the individual pair, the find gcd with // the previous element and add to the answer // and recur for the next element else ans = Math.Max(ans, __gcd(a[last], a[i]) + recur(i + 1, cnt + 1, 0, a, n, k, dp)); } return dp[ind,cnt] = ans; } static int __gcd( int a, int b) { if (b == 0) return a; return __gcd(b, a % b); } // Driver Code public static void Main(String[] args) { int []a = { 4, 5, 3, 7, 8, 10, 9, 8 }; int n = a.Length; int k = 4; int [,]dp = new int [n,MAX]; for ( int i = 0; i < n; i++) { for ( int j = 0; j < MAX; j++) { dp[i,j] = -1; } } Console.WriteLine(recur(0, 0, 0, a, n, k, dp)); } } // This code is contributed by Princi Singh |
Javascript
<script> // Javascript program to find the sum of // the addition of all possible subsets let MAX = 100; // Recursive function to find the maximum value of // the given recurrence function recur(ind,cnt,last,a,n,k,dp) { // If we get K elements if (cnt == k) return 0; // If we have reached the end // and K elements are not there if (ind == n) return -1e9; // If the state has been visited if (dp[ind][cnt] != -1) return dp[ind][cnt]; let ans = 0; // Iterate for every element as the // next possible element // and take the element which gives // the maximum answer for (let i = ind; i < n; i++) { // If this element is the first element // in the individual pair in the subsequence // then simply recurrence with the last // element as i-th index if (cnt % 2 == 0) ans = Math.max(ans,recur(i + 1, cnt + 1, i, a, n, k, dp)); // If this element is the second element in // the individual pair, the find gcd with // the previous element and add to the answer // and recur for the next element else ans = Math.max(ans, __gcd(a[last], a[i]) + recur(i + 1, cnt + 1, 0, a, n, k, dp)); } return dp[ind][cnt] = ans; } function __gcd(a,b) { if (b == 0) return a; return __gcd(b, a % b); } // Driver Code let a=[4, 5, 3, 7, 8, 10, 9, 8]; let n = a.length; let k = 4; let dp = new Array(n); for (let i=0;i<n;i++) { dp[i]= new Array(MAX); for (let j = 0; j < MAX; j++) { dp[i][j] = -1; } } document.write(recur(0, 0, 0, a, n, k, dp)); // This code is contributed by unknown2108 </script> |
9
Time Complexity: O(N*k), as we are using a loop to traverse N times and in each traversal we are recursively calling the function which will cost O(k) time. Where N is the number of elements in the array.
Auxiliary Space: O(N*100), as we are using extra space for the dp matrix. Where N is the number of elements in the array.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!