Maximize sum of GCD of two subsets of given Array
Given an array arr[] of positive integers of size N, the task is to divide the array into two non-empty subsets X and Y in such a way that the sum of their GCD turns out to be the maximum possible
Examples:
Input: N = 3, arr[] = {1, 2, 9}
Output: 10
Explanation: We can divide the array as
X = (1, 2) with GCD = 1
Y = (9) with GCD = 9
Maximum sum comes as 10Input: N = 4, arr[] = {7, 21, 27, 28}
Output: 34
Explanation: Possible divisions :
X= 7, 21, 28 with GCD = 7 and Y = 27 with GCD =27. Sum = 34
X = 7, 21, 27 with GCD = 1 and Y = 28 with GCD =28. Sum = 29
Use the first way for the maximum sum possible i.e., 34.
Approach: The problem can be solved based on the following idea:
To get the maximum GCD sum, keep the highest one in one subset (say X) and the others in another (say Y).
But it can give raise to a case where the second maximum unique element causes the GCD of Y = 1 but the maximum element when considered in Y and the second max in X then the GCD sum may be greater. (Happens when the maximum element when kept with elements of Y subset the GCD is greater than 1 but when 2nd largest was in Y it was 1).
We don’t need to consider for 3rd largest because if both first and second largest are divisible by the GCD then there difference is greater than the GCD[say a] and 3rd largest + a < 1 + largest as largest > 3rd largest+a
- So for gaining max gcd sum we will take gcd of smallest n-2 unique elements.
- Find including which one gives the greater sum.
Follow the below steps to understand better:
- First sort the array arr[].
- Traverse arr from i = 0 to i = N-1 and Find all the unique elements.
- If there was only one element then division in subsets is not possible.
- If only one unique element but more than once, then the same element will be present in both subsets.
- If there are only two unique elements after avoiding repetitions then return their sum.
- Take gcd of all elements except the last two:
- Check which is better to keep alone last or second last element.
- Return the maximum sum.
Below is the code for the above implementation:
C++
// C++ code for above approach #include <bits/stdc++.h> using namespace std; // Function for finding maximum value sum of // GCD of Subsets int SubMaxGCD( int N, vector< int >& A) { // If only one element if (A.size() == 1) return -1; // Sort the given array sort(A.begin(), A.end()); vector< int > v; // Running till last-1 element for ( int i = 0; i < N - 1; ++i) { // Avoiding repetitions // as GCD remains same if (A[i] == A[i + 1]) continue ; else v.push_back(A[i]); } // Pushing the last element // It avoids the case of // all the same element v.push_back(A[N - 1]); if (v.size() == 1) { // Returning if v.size is 1 // i.e. all elements are same return v[0] * 2; } // Corner case if there are only two // elements after avoiding repetitions if (v.size() == 2) { return v[0] + v[1]; } int n = v.size(); int g = v[0]; // Taking gcd of all elements // except last two elements for ( int i = 1; i < n - 2; ++i) { g = __gcd(g, v[i]); } // Check which is better to keep alone // last or second last element int gcd_a = __gcd(g, v[n - 2]) + v[n - 1]; int gcd_b = __gcd(g, v[n - 1]) + v[n - 2]; // Return the maximum sum. if (gcd_a >= gcd_b) return gcd_a; else return gcd_b; } // Driver code int main() { int N = 3; vector< int > arr = { 1, 2, 9 }; // Function call cout << SubMaxGCD(N, arr); return 0; } |
Java
// Java code for above approach import java.io.*; import java.util.*; class GFG { public static int gcd( int a, int b) { if (b == 0 ) return a; return gcd(b, a % b); } // Function for finding maximum value sum of // GCD of Subsets public static int SubMaxGCD( int N, int A[]) { // If only one element if (A.length == 1 ) return - 1 ; // Sort the given array Arrays.sort(A); ArrayList<Integer> v = new ArrayList<>(); // Running till last-1 element for ( int i = 0 ; i < N - 1 ; ++i) { // Avoiding repetitions // as GCD remains same if (A[i] == A[i + 1 ]) continue ; else v.add(A[i]); } // Pushing the last element // It avoids the case of // all the same element v.add(A[N - 1 ]); if (v.size() == 1 ) { // Returning if v.size is 1 // i.e. all elements are same return v.get( 0 ) * 2 ; } // Corner case if there are only two // elements after avoiding repetitions if (v.size() == 2 ) { return v.get( 0 ) + v.get( 1 ); } int n = v.size(); int g = v.get( 0 ); // Taking gcd of all elements // except last two elements for ( int i = 1 ; i < n - 2 ; ++i) { g = gcd(g, v.get(i)); } // Check which is better to keep alone // last or second last element int gcd_a = gcd(g, v.get(n - 2 )) + v.get(n - 1 ); int gcd_b = gcd(g, v.get(n - 1 )) + v.get(n - 2 ); // Return the maximum sum. if (gcd_a >= gcd_b) return gcd_a; else return gcd_b; } // Driver Code public static void main(String[] args) { int N = 3 ; int arr[] = { 1 , 2 , 9 }; // Function call System.out.print(SubMaxGCD(N, arr)); } } // This code is contributed by Rohit Pradhan |
Python3
# python3 code for above approach def gcd( a, b) : if (b = = 0 ) : return a return gcd(b, a % b) # Function for finding maximum value sum of # GCD of Subsets def SubMaxGCD( N, A) : # If only one element if len (A) = = 1 : return - 1 # Sort the given array A.sort() v = [] # Running till last-1 element for i in range (N - 1 ) : # Avoiding repetitions # as GCD remains same if A[i] = = A[i + 1 ] : continue else : v.append(A[i]) # Pushing the last element # It avoids the case of # all the same element v.append(A[N - 1 ]) if len (v) = = 1 : # Returning if v.size is 1 # i.e. all elements are same return v[ 0 ] * 2 # Corner case if there are only two # elements after avoiding repetitions if len (v) = = 2 : return v[ 0 ] + v[ 1 ] n = len (v) g = v[ 0 ] # Taking gcd of all elements # except last two elements for i in range (N - 2 ): g = gcd(g, v[i]) # Check which is better to keep alone # last or second last element gcd_a = gcd(g, v[n - 2 ]) + v[n - 1 ] gcd_b = gcd(g, v[n - 1 ]) + v[n - 2 ] # Return the maximum sum. if gcd_a > = gcd_b : return gcd_a else : return gcd_b # Driver Code if __name__ = = "__main__" : N = 3 arr = [ 1 , 2 , 9 ] # Function call print (SubMaxGCD(N, arr)) # This code is contributed by jana_sayantan. |
C#
// C# code for above approach using System; using System.Collections; class GFG { static int gcd( int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Function for finding maximum value sum of // GCD of Subsets static int SubMaxGCD( int N, int [] A) { // If only one element if (A.Length == 1) return -1; // Sort the given array Array.Sort(A); ArrayList v = new ArrayList(); // Running till last-1 element for ( int i = 0; i < N - 1; ++i) { // Avoiding repetitions // as GCD remains same if (A[i] == A[i + 1]) continue ; else v.Add(A[i]); } // Pushing the last element // It avoids the case of // all the same element v.Add(A[N - 1]); if (v.Count == 1) { // Returning if v.size is 1 // i.e. all elements are same return ( int )v[0] * 2; } // Corner case if there are only two // elements after avoiding repetitions if (v.Count == 2) { return ( int )v[0] + ( int )v[1]; } int n = v.Count; int g = ( int )v[0]; // Taking gcd of all elements // except last two elements for ( int i = 1; i < n - 2; ++i) { g = gcd(g, ( int )v[i]); } // Check which is better to keep alone // last or second last element int gcd_a = gcd(g, ( int )v[n - 2]) + ( int )v[n - 1]; int gcd_b = gcd(g, ( int )v[n - 1]) + ( int )v[n - 2]; // Return the maximum sum. if (gcd_a >= gcd_b) return gcd_a; else return gcd_b; } // Driver Code public static void Main() { int N = 3; int [] arr = { 1, 2, 9 }; // Function call Console.Write(SubMaxGCD(N, arr)); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for above approach // Function for GCD const __gcd = (a, b) => { if (b == 0) return a; return __gcd(b, a % b); } // Function for finding maximum value sum of // GCD of Subsets const SubMaxGCD = (N, A) => { // If only one element if (A.length == 1) return -1; // Sort the given array A.sort(); let v = []; // Running till last-1 element for (let i = 0; i < N - 1; ++i) { // Avoiding repetitions // as GCD remains same if (A[i] == A[i + 1]) continue ; else v.push(A[i]); } // Pushing the last element // It avoids the case of // all the same element v.push(A[N - 1]); if (v.length == 1) { // Returning if v.size is 1 // i.e. all elements are same return v[0] * 2; } // Corner case if there are only two // elements after avoiding repetitions if (v.length == 2) { return v[0] + v[1]; } let n = v.length; let g = v[0]; // Taking gcd of all elements // except last two elements for (let i = 1; i < n - 2; ++i) { g = __gcd(g, v[i]); } // Check which is better to keep alone // last or second last element let gcd_a = __gcd(g, v[n - 2]) + v[n - 1]; let gcd_b = __gcd(g, v[n - 1]) + v[n - 2]; // Return the maximum sum. if (gcd_a >= gcd_b) return gcd_a; else return gcd_b; } // Driver code let N = 3; let arr = [1, 2, 9]; // Function call document.write(SubMaxGCD(N, arr)); // This code is contributed by rakeshsahni. </script> |
10
Time Complexity: O(N * logN)
Auxiliary Space: O(N)