Find permutation which generates lexicographically largest Array of GCD of Prefixes
Given an array A[] of size N, find the permutation of array A such that the array B[] which is formed by taking the GCD of the prefixes of array A is lexicographically greatest among all possible arrays. Print the permutation of A and also B.
Note: If multiple answers are possible, print any of them
Examples:
Input: A[] = {2, 1, 4, 8, 16, 32, 5}
Output: A[] = {32, 16, 8, 4, 2, 5, 1}, B = {32, 16, 8, 4, 2, 1, 1}
Explanation: B[] = {gcd(32), gcd(32, 16), gcd(32, 16, 8), gcd(32, 16, 8, 4),
gcd(32, 16, 8, 4, 2), gcd(32, 16, 8, 4, 2, 1, 5), gcd(32, 16, 8, 4, 2, 1, 5)}Input: A[] = {5, 20, 21, 5, 17}
Output: A[] = {21, 20, 17, 5, 5 }, B[] = {21, 1, 1, 1, 1}
Naive Approach:
Iterate through all the permutations of A, find the gcd of the prefix of the array then sort all the arrays and print the greatest lexicographically array of gcd of the prefix.
Follow the steps mentioned below to implement the idea:
- Generate the permutation for the array.
- Iterate through the array and generate the B[] array from that permutation.
- Check if it is the lexicographically greatest and update accordingly.
- Return the permutation which generates the lexicographically largest B[].
Below is the code for the above-mentioned approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; pair<vector< int >, vector< int > > Findpermutation(vector< int >& A) { // We use this to save all possible result // from every permutations vector<pair<vector< int >, vector< int > > > sv; sort(A.begin(), A.end()); // This section used c++ stl to go through all // permutations of array A, but before that it needs to // be sorted, that's why we sorted above. do { int x = 0; // Find the gcd of prefix of array // for this permutation vector< int > B; // Go through elements of A // in this particular permutation for ( int i = 0; i < A.size(); i++) { x = __gcd(x, A[i]); B.push_back(x); } // The above logic is building B for this // permutation of A by using logic that // gcd(prefix[i]) = gcd(prefix[i-1], A[i]) for any i // and the initial value is taken as 0 because // GCD(0, A[i]) = A[i] sv.push_back({ B, A }); // Add this B into our all results. } while (next_permutation(A.begin(), A.end())); // We sort the results to find the best result, notice // we used greater<vector<int>() as sorting function sort(sv.begin(), sv.end()); // Return the first result because this is // lexicographically greatest. return sv.back(); } // Driver Code int main() { // This is the input array A vector< int > A = { 2, 1, 4, 8, 16, 32, 5 }; // Function call pair<vector< int >, vector< int > > result = Findpermutation(A); cout << "A = " ; for ( int i : result.second) { cout << i << ' ' ; } cout << endl; cout << "B = " ; for ( int i : result.first) { cout << i << ' ' ; } return 0; } |
Python3
import math def Findpermutation(A): # We use this to save all possible result # from every permutations sv = [] # Sort the input array A.sort() # This section uses Python's itertools library to go through all # permutations of the sorted array A. # Since Python's itertools library does not have a built-in function for next_permutation, # we use permutation instead of next_permutation to generate permutations of A. # We will generate all permutations of A, and apply the following logic to each one. for permutation in itertools.permutations(A): # Initialize gcd value as 0 x = 0 # Find the gcd of prefix of array for this permutation B = [] # Go through elements of A in this particular permutation for i in range ( len (permutation)): x = math.gcd(x, permutation[i]) B.append(x) # The above logic is building B for this permutation of A by using logic that # gcd(prefix[i]) = gcd(prefix[i-1], A[i]) for any i # and the initial value is taken as 0 because # GCD(0, A[i]) = A[i] sv.append((B, list (permutation))) # We sort the results to find the best result, notice # we used greater<vector<int>() as sorting function sv.sort(reverse = True ) # Return the first result because this is lexicographically greatest. return sv[ 0 ] # Driver Code import itertools if __name__ = = '__main__' : # This is the input array A A = [ 2 , 1 , 4 , 8 , 16 , 32 , 5 ] # Function call result = Findpermutation(A) print ( "A = " , end = "") for i in result[ 1 ]: print (i, end = " " ) print () print ( "B = " , end = "") for i in result[ 0 ]: print (i, end = " " ) |
C#
using System; using System.Collections.Generic; using System.Linq; public class Program { public static void Main() { // Driver Code int [] A = new int [] { 2, 1, 4, 8, 16, 32, 5 }; // Function call var result = FindPermutation(A); Console.WriteLine( "A = " + string .Join( " " , result.Item2)); Console.WriteLine( "B = " + string .Join( " " , result.Item1)); } public static Tuple< int [], int []> FindPermutation( int [] A) { List<Tuple< int [], int []> > sv = new List<Tuple< int [], int []> >(); // Sort the input array Array.Sort(A); // This section uses a permutation generator to go // through all permutations of the sorted array A. var permArr = Permute(A); foreach ( int [] permutation in permArr) { int x = 0; List< int > B = new List< int >(); for ( int j = 0; j < permutation.Length; j++) { x = Gcd(x, permutation[j]); B.Add(x); } sv.Add(Tuple.Create(B.ToArray(), permutation)); } // Sort the results to find the best result, notice // we used a lambda function as sorting function sv.Sort((a, b) => b.Item1.Sum() - a.Item1.Sum()); // Return the first result because this is // lexicographically greatest. return sv.First(); } public static int [][] Permute( int [] perms) { if (perms.Length <= 1) { return new [] { perms }; } List< int []> results = new List< int []>(); for ( int i = 0; i < perms.Length; i++) { int current = perms[i]; int [] remaining = perms.Take(i) .Concat(perms.Skip(i + 1)) .ToArray(); int [][] innerPermutations = Permute(remaining) .Select(p => new int [] { current } .Concat(p) .ToArray()) .ToArray(); results.AddRange(innerPermutations); } return results.ToArray(); } public static int Gcd( int a, int b) { if (b == 0) { return a; } return Gcd(b, a % b); } } // This code is contributed by phasing17 |
Javascript
// Javascript program for the above approach function findPermutation(A) { const sv = []; // Sort the input array A.sort((a, b) => a - b); // This section uses JavaScript's built-in permutation // function to go through all permutations of the sorted array A. const permArr = permute(A); for (let i = 0; i < permArr.length; i++) { const permutation = permArr[i]; let x = 0; const B = []; for (let j = 0; j < permutation.length; j++) { x = gcd(x, permutation[j]); B.push(x); } sv.push([B, permutation]); } // Sort the results to find the best result, // notice we used greater<vector<int>() as sorting function sv.sort((a, b) => { const aSum = a[0].reduce((acc, val) => acc + val, 0); const bSum = b[0].reduce((acc, val) => acc + val, 0); return bSum - aSum; }); // Return the first result because this is lexicographically greatest. return sv[0]; } function permute(perms) { if (perms.length <= 1) { return [perms]; } const results = []; for (let i = 0; i < perms.length; i++) { const current = perms[i]; const remaining = perms.slice(0, i).concat(perms.slice(i + 1)); const innerPermutations = permute(remaining); for (let j = 0; j < innerPermutations.length; j++) { results.push([current].concat(innerPermutations[j])); } } return results; } function gcd(a, b) { if (b === 0) { return a; } return gcd(b, a % b); } // Driver Code const A = [2, 1, 4, 8, 16, 32, 5]; // Function call const result = findPermutation(A); console.log(`A = ${result[1].join( " " )}`); console.log(`B = ${result[0].join( " " )}`); // This code is contributed by princekumaras |
Java
import java.util.*; public class Main { public static void main(String[] args) { int [] A = { 2 , 1 , 4 , 8 , 16 , 32 , 5 }; // Call the findPermutation method on A and store the result int [][] result = findPermutation(A); // Print the lexicographically greatest permutation of A and its corresponding B System.out.print( "A = " ); for ( int i = 0 ; i < result[ 1 ].length; i++) { System.out.print(result[ 1 ][i] + " " ); } System.out.println(); System.out.print( "B = " ); for ( int i = 0 ; i < result[ 0 ].length; i++) { System.out.print(result[ 0 ][i] + " " ); } } public static int [][] findPermutation( int [] A) { // Create an ArrayList to store all possible values of B and its corresponding permutation List< int [][]> sv = new ArrayList<>(); // Sort the input array Arrays.sort(A); // This section uses permutation to go through all permutations of the sorted array A. List< int []> permArr = permute(A); // Iterate through each permutation and calculate its corresponding B for ( int i = 0 ; i < permArr.size(); i++) { // Get the current permutation int [] permutation = permArr.get(i); // Initialize variables to calculate the greatest common divisor and B int x = 0 ; int [] B = new int [A.length]; // Iterate through each element in the current permutation and calculate B for ( int j = 0 ; j < permutation.length; j++) { // Calculate the greatest common divisor x = gcd(x, permutation[j]); // Set the corresponding element in B to the greatest common divisor B[j] = x; } // Add the current B and its corresponding permutation to the ArrayList sv.add( new int [][]{B, permutation}); } // Sort the results to find the best result Collections.sort(sv, (a, b) -> { int aSum = 0 ; int bSum = 0 ; for ( int i = 0 ; i < a[ 0 ].length; i++) { aSum += a[ 0 ][i]; bSum += b[ 0 ][i]; } return Integer.compare(bSum, aSum); }); // Return the first result because this is lexicographically greatest. return sv.get( 0 ); } public static List< int []> permute( int [] perms) { // Create an ArrayList to store all permutations List< int []> results = new ArrayList<>(); // If the input array has length 0 or 1, return it as a single permutation if (perms.length <= 1 ) { results.add(perms); return results; } // Iterate through each element in the input array for ( int i = 0 ; i < perms.length; i++) { // Get the current element int current = perms[i]; // Create a new array with all elements except the current one int [] remaining = new int [perms.length - 1 ]; System.arraycopy(perms, 0 , remaining, 0 , i); System.arraycopy(perms, i + 1 , remaining, i, perms.length - i - 1 ); // Recursively generate all permutations of the remaining elements List< int []> innerPermutations = permute(remaining); for ( int j = 0 ; j < innerPermutations.size(); j++) { int [] innerPermutation = innerPermutations.get(j); int [] res = new int [perms.length]; res[ 0 ] = current; System.arraycopy(innerPermutation, 0 , res, 1 , innerPermutation.length); results.add(res); } } return results; } public static int gcd( int a, int b) { if (b == 0 ) { return a; } return gcd(b, a % b); } } |
A = 32 16 8 4 2 5 1 B = 32 16 8 4 2 1 1
Time Complexity: O(N * N!), N! to find the permutation and N to iterate on each permutations.
Auxiliary Space: O(N)
Efficient Approach:
Iterate all the elements and for each element:
- Traverse all the other elements and find which element gives the greatest GCD among them.
- That will the be next element because it will generate a greater GCD for the B[] array.
Continue this process till the array is built.
Follow the steps mentioned below to implement the idea:
- Initially store a GCD = 0 (to get the max gcd in next step, because gcd(0, x) = x)
- Traverse from i = 0 to N:
- Iterate from j = 0 to N.
- If the gcd of A[j] with the previous gcd is maximum update the gcd value.
- Put A[j] and the maximum GCD in the resultant arrays.
- Iterate from j = 0 to N.
- When the iteration is over, return the resultant arrays.
Below is the implementation for the above approach
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to find the permutation pair<vector< int >, vector< int > > Findpermutation(vector< int >& A) { // This array to mark the elements // as used so we don't use again. vector< bool > used(A.size(), 0); // This will save our result vector< int > ansA; vector< int > ansB; int x = 0; for ( int i = 0; i < A.size(); i++) { // This code segment finds // the next best element for // max gcd of prefix int temp = 0, mx_gcd = 0, index = -1; // We start with temp, mx_gcd as 0 // because of gcd property // GCD(0, x) = x for ( int j = 0; j < A.size(); j++) { if (!used[j]) { // We are taking gcd with x temp = __gcd(x, A[j]); // If this gcd is better than before // then take this as new index. if (temp > mx_gcd) { mx_gcd = temp; index = j; } } } // Take the new best gcd and // merge with the previous result x = __gcd(x, mx_gcd); // Mark the element as used used[index] = 1; // Add the element to answer ansB.push_back(x); ansA.push_back(A[index]); } return { ansA, ansB }; } // Driver Code int main() { vector< int > A = { 2, 1, 4, 8, 16, 32, 5 }; // Function call pair<vector< int >, vector< int > > ans = Findpermutation(A); cout << "A = " ; for ( int i : ans.first) { cout << i << ' ' ; } cout << endl; cout << "B = " ; for ( int i : ans.second) { cout << i << ' ' ; } return 0; } |
Java
// Java code to implement the approach import java.io.*; import java.util.*; class pair { List<Integer> first = new ArrayList<>(); List<Integer> second = new ArrayList<>(); public pair(List<Integer> first, List<Integer> second) { this .first = first; this .second = second; } } class GFG { static int gcd( int a, int b) { if (b == 0 ) return a; return gcd(b, a % b); } // Function to find the permutation static pair Findpermutation( int [] A) { // This array to mark the elements // as used so we don't use again. boolean [] used = new boolean [A.length]; Arrays.fill(used, Boolean.FALSE); List<Integer> ansA = new ArrayList<>(); List<Integer> ansB = new ArrayList<>(); int x = 0 ; for ( int i = 0 ; i < A.length; i++) { // This code segment finds // the next best element for // max gcd of prefix int temp = 0 , mx_gcd = 0 , index = - 1 ; // We start with temp, mx_gcd as 0 // because of gcd property // GCD(0, x) = x for ( int j = 0 ; j < A.length; j++) { if (!used[j]) { // We are taking gcd with x temp = gcd(x, A[j]); // If this gcd is better than before // then take this as new index. if (temp > mx_gcd) { mx_gcd = temp; index = j; } } } // Take the new best gcd and // merge with the previous result x = gcd(x, mx_gcd); // Mark the element as used used[index] = true ; // Add the element to answer ansB.add(x); ansA.add(A[index]); } return new pair(ansA, ansB); } public static void main(String[] args) { int [] A = { 2 , 1 , 4 , 8 , 16 , 32 , 5 }; // Function call pair ans = Findpermutation(A); System.out.print( "A = " ); for ( int i = 0 ; i < ans.first.size(); i++) { System.out.print(ans.first.get(i) + " " ); } System.out.println(); System.out.print( "B = " ); for ( int i = 0 ; i < ans.second.size(); i++) { System.out.print(ans.second.get(i) + " " ); } } } // This is contributed by lokesh |
Python3
import math # Function to find the permutation def Findpermutation(A): # This array to mark the elements # as used so we don't use again. used = [ False ] * len (A) # This will save our result ansA = [] ansB = [] x = 0 for i in range ( len (A)): # This code segment finds # the next best element for # max gcd of prefix temp = 0 mx_gcd = 0 index = - 1 # We start with temp, mx_gcd as 0 # because of gcd property # GCD(0, x) = x for j in range ( len (A)): if not used[j]: # We are taking gcd with x temp = math.gcd(x, A[j]) # If this gcd is better than before # then take this as new index. if temp > mx_gcd: mx_gcd = temp index = j # Take the new best gcd and # merge with the previous result x = math.gcd(x, mx_gcd) # Mark the element as used used[index] = True # Add the element to answer ansB.append(x) ansA.append(A[index]) return (ansA, ansB) # Driver Code A = [ 2 , 1 , 4 , 8 , 16 , 32 , 5 ] # Function call ans = Findpermutation(A) print ( "A = " , end = "") print ( * ans[ 0 ]) print ( "B = " , end = "") print ( * ans[ 1 ]) |
C#
// c# code to implement the approach using System; using System.Collections.Generic; class pair { public List< int > first = new List< int >(); public List< int > second = new List< int >(); public pair(List< int > first, List< int > second) { this .first = first; this .second = second; } } class GFG { static int gcd( int a, int b) { if (b == 0) { return a; } return gcd(b, a % b); } // Function to find the permutation static pair Findpermutation( int [] A) { // This array to mark the elements // as used so we don't use again. bool [] used = new bool [A.Length]; for ( int i = 0; i < A.Length; i++) { used[i] = false ; } List< int > ansA = new List< int >(); List< int > ansB = new List< int >(); int x = 0; for ( int i = 0; i < A.Length; i++) { // This code segment finds // the next best element for // max gcd of prefix int temp = 0, mx_gcd = 0, index = -1; // We start with temp, mx_gcd as 0 // because of gcd property // GCD(0, x) = x for ( int j = 0; j < A.Length; j++) { if (!used[j]) { // We are taking gcd with x temp = gcd(x, A[j]); // If this gcd is better than before // then take this as new index. temp = gcd(x, A[j]); if (temp > mx_gcd) { mx_gcd = temp; index = j; } } } // Take the new best gcd and // merge with the previous result x = gcd(x, mx_gcd); used[index] = true ; ansB.Add(x); ansA.Add(A[index]); } return new pair(ansA, ansB); } static void Main( string [] args) { int [] A = { 2, 1, 4, 8, 16, 32, 5 }; // Function call pair ans = Findpermutation(A); Console.Write( "A = " ); for ( int i = 0; i < ans.first.Count; i++) { Console.Write(ans.first[i] + " " ); } Console.WriteLine(); Console.Write( "B = " ); for ( int i = 0; i < ans.second.Count; i++) { Console.Write(ans.second[i] + " " ); } } } |
Javascript
// JavaScript code for the above approach function __gcd(a, b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a - b, b); return __gcd(a, b - a); } // Function to find the permutation function Findpermutation(A) { // This array to mark the elements // as used so we don't use again. let used = new Array(A.length).fill(0); // This will save or result let ansA = []; let ansB = []; let x = 0; for (let i = 0; i < A.length; i++) { // This code segment finds // the next best element for // max gcd of prefix let temp = 0, mx_gcd = 0, index = -1; // We start with temp, mx_gcd as 0 // because of gcd property // GCD(0, x) = x for (let j = 0; j < A.length; j++) { if (!used[j]) { // We are taking gcd with x temp = __gcd(x, A[j]); // If this gcd is better than before // then take this as new index. if (temp > mx_gcd) { mx_gcd = temp; index = j; } } } // Take the new best gcd and // merge with the previous result x = __gcd(x, mx_gcd); // Mark the element as used used[index] = 1; // Add the element to answer ansB.push(x); ansA.push(A[index]); } return [ansA, ansB]; } // Driver Code let A = [2, 1, 4, 8, 16, 32, 5]; // Function call let ans = Findpermutation(A); console.log( "A = " ); for (let i of ans[0]) { console.log(i + " " ); } console.log( "<br>" ) console.log( "B = " ); for (let i of ans[1]) { console.log(i + " " ); } console.log( "<br>" ) // This code is contributed by Potta Lokesh. |
A = 32 16 8 4 2 1 5 B = 32 16 8 4 2 1 1
Time Complexity: O(N2)
Auxiliary Space: O(N)
Contact Us