Discover permutation which generates lexicographically largest Array of GCD of Prefixes

Given an array A[] of dimension N, discover the permutation of array A such that the array B[] which is shaped by taking the GCD of the prefixes of array A is lexicographically best amongst all doable arrays. Print the permutation of A and in addition B. 

Word: If a number of solutions are doable, print any of them

Examples:

Enter: 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}
Rationalization: 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)}  

Enter: A[] =  {5, 20, 21, 5, 17}
Output: A[] = {21, 20, 17, 5, 5 }, B[] = {21, 1, 1, 1, 1}

Naive Method: 

Iterate by way of all of the permutations of A, discover the gcd of the prefix of the array then kind all of the arrays and print the best lexicographically array of gcd of the prefix.

Observe the steps talked about beneath to implement the thought:

• Generate the permutation for the array.
  • Iterate by way of the array and generate the B[] array from that permutation.
  • Examine if it’s the lexicographically best and replace accordingly.
• Return the permutation which generates the lexicographically largest B[].

Beneath is the code for the above-mentioned method:

A = 32 16 8 4 2 5 1 
B = 32 16 8 4 2 1 1 

Time Complexity: O(N * N!), N! to seek out the permutation and N to iterate on every permutations.
Auxiliary Area: O(1)

Environment friendly Method: 

Iterate all the weather and for every aspect:

• Treverse  all the opposite parts and discover which aspect provides the best GCD amongst them.
• That may the be subsequent aspect as a result of it should generate a larger GCD for the B[] array. 

Continuen this course of until the array is constructed.

Observe the steps talked about beneath to implement the thought:

• Initially retailer a GCD = 0 (to get the max gcd in subsequent step, as a result of gcd(0, x) = x)
• Traverse from i = 0 to N:
  • Iterate from j = 0 to N.
    • If the gcd of A[j] with the earlier gcd is most replace the gcd worth.
  • Put A[j] and the utmost GCD within the resultant arrays.
• When the iteration is over, return the resultant arrays.

Beneath is the implementation for the above method

A = 32 16 8 4 2 1 5 
B = 32 16 8 4 2 1 1 

Time Complexity: O(N²)
Auxiliary Area: O(N)