Given an array arr[] consisting of a permutation of first N natural numbers, the task is to find the maximum possible value of ?GCD(arr[i], i) (1-based indexing) by rearranging the given array elements.
Examples:
Input: arr[] = { 2, 1}
Output: 6
Explanation:
Rearranging the given array to { 2, 1}.
?GCD(arr[i], i) = GCD(arr[1], 1) + GCD(arr[2], 2) = GCD(2, 1) + GCD(1, 2)= 2
Rearranging the given array to { 1, 2 }.
?GCD(arr[i], i) = GCD(arr[1], 1) + GCD(arr[2], 2) = GCD(1, 1) + GCD(2, 2) = 3
Therefore, the required output is 3Input: arr[] = { 4, 5, 3, 2, 1 }
Output: 15
Naive Approach: The simplest approach to solve the problem is to traverse the array and generate all possible permutations of the given array and for each permutation, find the value of ?GCD(arr[i], i). Finally, print the maximum value of ?GCD(arr[i], i) from each permutation.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum sum of// GCD(arr[i], i) by rearranging the arrayint findMaxValByRearrArr(int arr[], int N){ // Sort the array in // ascending order sort(arr, arr + N); // Stores maximum sum of GCD(arr[i], i) // by rearranging the array elements int res = 0; // Generate all possible // permutations of the array do { // Stores sum of GCD(arr[i], i) int sum = 0; // Traverse the array for (int i = 0; i < N; i++) { // Update sum sum += __gcd(i + 1, arr[i]); } // Update res res = max(res, sum); } while (next_permutation(arr, arr + N)); return res;}// Driver Codeint main(){ int arr[] = { 3, 2, 1 }; int N = sizeof(arr) / sizeof(arr[0]); cout << findMaxValByRearrArr(arr, N); return 0;} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{ // Function to find the maximum sum of // GCD(arr[i], i) by rearranging the array static int findMaxValByRearrArr(int arr[], int N) { // Sort the array in // ascending order Arrays.sort(arr); // Stores maximum sum of GCD(arr[i], i) // by rearranging the array elements int res = 0; // Generate all possible // permutations of the array do { // Stores sum of GCD(arr[i], i) int sum = 0; // Traverse the array for (int i = 0; i < N; i++) { // Update sum sum += __gcd(i + 1, arr[i]); } // Update res res = Math.max(res, sum); } while (next_permutation(arr)); return res; } static int __gcd(int a, int b) { return b == 0? a:__gcd(b, a % b); } static boolean next_permutation(int[] p) { for (int a = p.length - 2; a >= 0; --a) if (p[a] < p[a + 1]) for (int b = p.length - 1;; --b) if (p[b] > p[a]) { int t = p[a]; p[a] = p[b]; p[b] = t; for (++a, b = p.length - 1; a < b; ++a, --b) { t = p[a]; p[a] = p[b]; p[b] = t; } return true; } return false; } // Driver Code public static void main(String[] args) { int arr[] = { 3, 2, 1 }; int N = arr.length; System.out.print(findMaxValByRearrArr(arr, N)); }}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to implement# the above approach# Function to find the maximum sum of# GCD(arr[i], i) by rearranging the arraydef findMaxValByRearrArr(arr, N): # Sort the array in # ascending order arr.sort() # Stores maximum sum of GCD(arr[i], i) # by rearranging the array elements res = 0 # Generate all possible # permutations of the array while (True): # Stores sum of GCD(arr[i], i) Sum = 0 # Traverse the array for i in range(N): # Update sum Sum += __gcd(i + 1, arr[i]) # Update res res = max(res, Sum) if (not next_permutation(arr)): break return res def __gcd(a, b): if b == 0: return a else: return __gcd(b, a % b)def next_permutation(p): for a in range(len(p) - 2, -1, -1): if (p[a] < p[a + 1]): b = len(p) - 1 while True: if (p[b] > p[a]): t = p[a] p[a] = p[b] p[b] = t a += 1 b = len(p) - 1 while a < b: t = p[a] p[a] = p[b] p[b] = t a += 1 b -= 1 return True b -= 1 return False# Driver code arr = [ 3, 2, 1 ]N = len(arr)print(findMaxValByRearrArr(arr, N))# This code is contributed by divyesh072019 |
C#
// C# program to implement// the above approachusing System;class GFG{ // Function to find the maximum sum of // GCD(arr[i], i) by rearranging the array static int findMaxValByRearrArr(int []arr, int N) { // Sort the array in // ascending order Array.Sort(arr); // Stores maximum sum of GCD(arr[i], i) // by rearranging the array elements int res = 0; // Generate all possible // permutations of the array do { // Stores sum of GCD(arr[i], i) int sum = 0; // Traverse the array for (int i = 0; i < N; i++) { // Update sum sum += __gcd(i + 1, arr[i]); } // Update res res = Math.Max(res, sum); } while (next_permutation(arr)); return res; } static int __gcd(int a, int b) { return b == 0? a:__gcd(b, a % b); } static bool next_permutation(int[] p) { for (int a = p.Length - 2; a >= 0; --a) if (p[a] < p[a + 1]) for (int b = p.Length - 1;; --b) if (p[b] > p[a]) { int t = p[a]; p[a] = p[b]; p[b] = t; for (++a, b = p.Length - 1; a < b; ++a, --b) { t = p[a]; p[a] = p[b]; p[b] = t; } return true; } return false; } // Driver Code public static void Main(String[] args) { int []arr = { 3, 2, 1 }; int N = arr.Length; Console.Write(findMaxValByRearrArr(arr, N)); }} // This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program to implement// the above approach // Function to find the maximum sum of // GCD(arr[i], i) by rearranging the array function findMaxValByRearrArr(arr, N) { // Sort the array in // ascending order arr.sort(); // Stores maximum sum of GCD(arr[i], i) // by rearranging the array elements let res = 0; // Generate all possible // permutations of the array do { // Stores sum of GCD(arr[i], i) let sum = 0; // Traverse the array for (let i = 0; i < N; i++) { // Update sum sum += __gcd(i + 1, arr[i]); } // Update res res = Math.max(res, sum); } while (next_permutation(arr)); return res; } function __gcd(a, b) { return b == 0? a:__gcd(b, a % b); } function next_permutation(p) { for (let a = p.length - 2; a >= 0; --a) if (p[a] < p[a + 1]) for (let b = p.length - 1;; --b) if (p[b] > p[a]) { let t = p[a]; p[a] = p[b]; p[b] = t; for (++a, b = p.length - 1; a < b; ++a, --b) { t = p[a]; p[a] = p[b]; p[b] = t; } return true; } return false; }// Driver Code let arr = [ 3, 2, 1 ]; let N = arr.length; document.write(findMaxValByRearrArr(arr, N)); // This code is contributed by souravghosh0416.</script> |
Output:
6
Time Complexity: O(N!)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the following observations:
Maximum possible value of GCD(X, Y) = min(X, Y)
Therefore, the maximum possible value of GCD(i, arr[i]) = min(i, arr[i])
If array is sorted then i = arr[i] and the value of GCD(i, arr[i]) = i
?GCD(arr[i], i) = ?i = N * (N + 1) / 2
Follow the steps below to solve the problem:
- Initialize a variable, say res, to store the maximum possible sum of ?GCD(arr[i], i).
- Update res = (N * (N + 1) / 2).
- Finally, print the value of res.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum sum of// GCD(arr[i], i) by rearranging the arrayint findMaxValByRearrArr(int arr[], int N){ // Stores maximum sum of GCD(arr[i], i) // by rearranging the array elements int res = 0; // Update res res = (N * (N + 1)) / 2; return res;}// Driver Codeint main(){ int arr[] = { 3, 2, 1 }; int N = sizeof(arr) / sizeof(arr[0]); cout << findMaxValByRearrArr(arr, N); return 0;} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{// Function to find the maximum sum of// GCD(arr[i], i) by rearranging the arraystatic int findMaxValByRearrArr(int arr[], int N){ // Stores maximum sum of GCD(arr[i], i) // by rearranging the array elements int res = 0; // Update res res = (N * (N + 1)) / 2; return res;}// Driver Codepublic static void main(String[] args){ int arr[] = { 3, 2, 1 }; int N = arr.length; System.out.print(findMaxValByRearrArr(arr, N));}}// This code is contributed by shikhasingrajput |
Python3
# Python program to implement# the above approach# Function to find the maximum sum of# GCD(arr[i], i) by rearranging the arraydef findMaxValByRearrArr(arr, N): # Stores maximum sum of GCD(arr[i], i) # by rearranging the array elements res = 0; # Update res res = (N * (N + 1)) // 2; return res;# Driver Codeif __name__ == '__main__': arr = [ 3, 2, 1 ]; N = len(arr); print(findMaxValByRearrArr(arr, N));# This code contributed by shikhasingrajput |
C#
// C# program to implement// the above approachusing System;class GFG{ // Function to find the maximum sum of// GCD(arr[i], i) by rearranging the arraystatic int findMaxValByRearrArr(int []arr, int N){ // Stores maximum sum of GCD(arr[i], i) // by rearranging the array elements int res = 0; // Update res res = (N * (N + 1)) / 2; return res;}// Driver Codepublic static void Main(String[] args){ int []arr = { 3, 2, 1 }; int N = arr.Length; Console.Write(findMaxValByRearrArr(arr, N));}}// This code is contributed by shikhasingrajput |
Javascript
<script> // Javascript program to implement // the above approach // Function to find the maximum sum of // GCD(arr[i], i) by rearranging the array function findMaxValByRearrArr(arr, N) { // Stores maximum sum of GCD(arr[i], i) // by rearranging the array elements let res = 0; // Update res res = parseInt((N * (N + 1)) / 2, 10); return res; } let arr = [ 3, 2, 1 ]; let N = arr.length; document.write(findMaxValByRearrArr(arr, N));</script> |
Output:
6
Time Complexity: O(1)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
