Rearrange array to obtain maximum possible value of concatenation of prefix GCDs
Given an array arr[] consisting of N positive integers, the task is to rearrange the array elements such that the number formed by concatenating the GCD of elements of the array arr[] from index 0 to i for each index i is the maximum possible.
Examples:
Input: arr[] = {4, 2, 5}
Output: 5 4 2
Explanation:
X = 511 is the maximum value of X that can be obtained among all the rearrangement of arr[].
Possible arrangements of arr[] are:
arr[] = [2, 4, 5] ? X = 221
arr[] = [2, 5, 4] ? X = 211
arr[] = [4, 2, 5] ? X = 421
arr[] = [4, 5, 2] ? X = 411
arr[] = [5, 4, 2] ? X = 511
arr[] = [5, 2, 4] ? X = 511Input: arr[] = {2, 4, 6, 8}
Output: 8 4 6 2
Explanation:
X = 842 is the maximum value of X that can be obtained among all the rearrangement of arr[].
Possible arrangements of arr[] are:
arr[] = [4, 6, 8] ? X = 422
arr[] = [4, 8, 6] ? X = 442
arr[] = [6, 4, 8] ? X = 622
arr[] = [6, 8, 4] ? X = 622
arr[] = [8, 4, 6] ? X = 842
arr[] = [8, 6, 4] ? X = 822
Approach: The GCD of a number alone is the number itself, thus the first digit of X i.e., X[0] would always be equal to arr[0]. Thus, to ensure that X is maximum among all obtainable numbers, arr[0] needs to be maximum. Then proceed by keeping track of the GCD of the longest prefix of arr[] that has been already arranged and find the values of the consecutive elements to be placed after this prefix. Follow the steps below to solve the above problem:
- The largest element of the array is set as the first element, thus the first prefix correctly arranged in the array arr[].
- Now find the element consecutive to the last element of the prefix i.e., arr[1].
- Here the GCD of the longest prefix(say G) is equal to arr[0], thus traverse the remaining array to find the element that gives the greatest GCD with G.
- Now, swap the element arr[1] with the element that gives maximum GCD with value G, update the value of G to this maximum GCD obtained i.e., G = GCD(G, arr[1]).
- Now the longest fixed prefix becomes arr[0], arr[1], continue this process for finding arr[2], arr[3], …, arr[N – 1], to obtain the required array.
- Print rearrange array after the above steps.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum number // obtainable from prefix GCDs void prefixGCD( int arr[], int N) { // Stores the GCD of the // longest prefix int gcc; // Sort the array sort(arr, arr + N); // Reverse the array reverse(arr, arr + N); // GCD of a[0] is a[0] gcc = arr[0]; int start = 0; // Iterate to place the arr[start + 1] // element at it's correct position while (start < N - 1) { int g = 0, s1; for ( int i = start + 1; i < N; i++) { // Find the element with // maximum GCD int gc = __gcd(gcc, arr[i]); // Update the value of g if (gc > g) { g = gc; s1 = i; } } // Update GCD of prefix gcc = g; // Place arr[s1] to it's // correct position swap(arr[s1], arr[start + 1]); // Increment start for the // remaining elements start++; } // Print the rearranged array for ( int i = 0; i < N; i++) { cout << arr[i] << " " ; } } // Driver Code int main() { // Given array arr[] int arr[] = { 1, 2, 3, 4 }; int N = sizeof (arr) / sizeof (arr[0]); // Function Call prefixGCD(arr, N); return 0; } |
Java
//Java program for // the above approach import java.util.*; class GFG{ //Function to find the maximum number //obtainable from prefix GCDs static void prefixGCD( int arr[], int N) { // Stores the GCD of the // longest prefix int gcc; // Sort the array Arrays.sort(arr); // Reverse the array arr = reverse(arr); // GCD of a[0] is a[0] gcc = arr[ 0 ]; int start = 0 ; // Iterate to place // the arr[start + 1] // element at it's // correct position while (start < N - 1 ) { int g = 0 , s1 = 0 ; for ( int i = start + 1 ; i < N; i++) { // Find the element with // maximum GCD int gc = __gcd(gcc, arr[i]); // Update the value of g if (gc > g) { g = gc; s1 = i; } } // Update GCD of prefix gcc = g; // Place arr[s1] to it's // correct position arr = swap(arr, s1, start + 1 ); // Increment start for the // remaining elements start++; } // Print the rearranged array for ( int i = 0 ; i < N; i++) { System.out.print(arr[i] + " " ); } } static int __gcd( int a, int b) { return b == 0 ? a : __gcd(b, a % b); } static int [] reverse( int a[]) { int i, n = a.length, t; for (i = 0 ; i < n / 2 ; i++) { t = a[i]; a[i] = a[n - i - 1 ]; a[n - i - 1 ] = t; } return a; } static int [] swap( int []arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr; } //Driver Code public static void main(String[] args) { // Given array arr[] int arr[] = { 1 , 2 , 3 , 4 }; int N = arr.length; // Function Call prefixGCD(arr, N); } } //This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approach from math import gcd # Function to find the maximum number # obtainable from prefix GCDs def prefixGCD(arr, N): # Stores the GCD of the # longest prefix gcc = 0 # Sort the array arr = sorted (arr) # Reverse the array arr = arr[:: - 1 ] # GCD of a[0] is a[0] gcc = arr[ 0 ] start = 0 # Iterate to place the arr[start + 1] # element at it's correct position while (start < N - 1 ): g = 0 s1 = 0 for i in range (start + 1 , N): # Find the element with # maximum GCD gc = gcd(gcc, arr[i]) # Update the value of g if (gc > g): g = gc s1 = i # Update GCD of prefix gcc = g # Place arr[s1] to it's # correct position arr[s1], arr[start + 1 ] = arr[start + 1 ], arr[s1] # Increment start for the # remaining elements start + = 1 # Print the rearranged array for i in range (N): print (arr[i], end = " " ) # Driver Code if __name__ = = '__main__' : # Given array arr[] arr = [ 1 , 2 , 3 , 4 ] N = len (arr) # Function Call prefixGCD(arr, N) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System; class GFG{ // Function to find the maximum number // obtainable from prefix GCDs static void prefixGCD( int [] arr, int N) { // Stores the GCD of the // longest prefix int gcc; // Sort the array Array.Sort(arr); // Reverse the array arr = reverse(arr); // GCD of a[0] is a[0] gcc = arr[0]; int start = 0; // Iterate to place the // arr[start + 1] element // at it's correct position while (start < N - 1) { int g = 0, s1 = 0; for ( int i = start + 1; i < N; i++) { // Find the element with // maximum GCD int gc = __gcd(gcc, arr[i]); // Update the value of g if (gc > g) { g = gc; s1 = i; } } // Update GCD of prefix gcc = g; // Place arr[s1] to it's // correct position arr = swap(arr, s1, start + 1); // Increment start for the // remaining elements start++; } // Print the rearranged array for ( int i = 0; i < N; i++) { Console.Write(arr[i] + " " ); } } static int __gcd( int a, int b) { return b == 0 ? a : __gcd(b, a % b); } static int [] reverse( int [] a) { int i, n = a.Length, t; for (i = 0; i < n / 2; i++) { t = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = t; } return a; } static int [] swap( int []arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr; } //Driver Code public static void Main() { // Given array arr[] int [] arr = { 1, 2, 3, 4 }; int N = arr.Length; // Function call prefixGCD(arr, N); } } // This code is contributed by sanjoy_62 |
Javascript
<script> // Javascript program to implement // the above approach //Function to find the maximum number //obtainable from prefix GCDs function prefixGCD(arr, N) { // Stores the GCD of the // longest prefix let gcc; // Sort the array arr.sort(); // Reverse the array arr = reverse(arr); // GCD of a[0] is a[0] gcc = arr[0]; let start = 0; // Iterate to place // the arr[start + 1] // element at it's // correct position while (start < N - 1) { let g = 0, s1 = 0; for (let i = start + 1; i < N; i++) { // Find the element with // maximum GCD let gc = __gcd(gcc, arr[i]); // Update the value of g if (gc > g) { g = gc; s1 = i; } } // Update GCD of prefix gcc = g; // Place arr[s1] to it's // correct position arr = swap(arr, s1, start + 1); // Increment start for the // remaining elements start++; } // Print the rearranged array for (let i = 0; i < N; i++) { document.write(arr[i] + " " ); } } function __gcd(a, b) { return b == 0 ? a : __gcd(b, a % b); } function reverse(a) { let i, n = a.length, t; for (i = 0; i < n / 2; i++) { t = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = t; } return a; } function swap(arr, i, j) { let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr; } // Driver Code // Given array arr[] let arr = [1, 2, 3, 4]; let N = arr.length; // Function Call prefixGCD(arr, N); </script> |
4 2 3 1
Time Complexity: O(N2)
Auxiliary Space: O(1)
Contact Us