Rearrange array to maximize sum of GCD of array elements with their respective indices

0 0 8 minutes read

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 3

Input: 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 array
int 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 Code
int 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 approach
import 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 array
def 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 approach
using 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:

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 array
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 Code
int 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 approach
import 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)
{
 
    // 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 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 shikhasingrajput

Python3

# Python program to implement
# the above approach
 
# Function to find the maximum sum of
# GCD(arr[i], i) by rearranging the array
def 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 Code
if __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 approach
using 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)
{
     
    // 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 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 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:

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 zambiatek!