Discover permutation which generates lexicographically largest Array of GCD of Prefixes

0
7


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

Observe: 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}
Clarification: 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 Strategy: 

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

Comply with the steps talked about beneath to implement the thought:

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

Beneath is the code for the above-mentioned method:

C++

#embody <bits/stdc++.h>

utilizing namespace std;

  

pair<vector<int>, vector<int> >

Findpermutation(vector<int>& A)

{

    

    

    vector<pair<vector<int>, vector<int> > > sv;

    type(A.start(), A.finish());

  

    

    

    

    do {

        int x = 0;

  

        

        

        vector<int> B;

  

        

        

        for (int i = 0; i < A.dimension(); i++) {

            x = __gcd(x, A[i]);

            B.push_back(x);

        }

  

        

        

        

        

        

        sv.push_back({ B, A });

  

        

    } whereas (next_permutation(A.start(), A.finish()));

  

    

    

    type(sv.start(), sv.finish());

  

    

    

    return sv.again();

}

  

int primary()

{

  

    

    vector<int> A = { 2, 1, 4, 8, 16, 32, 5 };

  

    

    pair<vector<int>, vector<int> > end result

        = Findpermutation(A);

    cout << "A = ";

    for (int i : end result.second) {

        cout << i << ' ';

    }

    cout << endl;

  

    cout << "B = ";

    for (int i : end result.first) {

        cout << i << ' ';

    }

    return 0;

}

Output

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 Strategy: 

Iterate all the weather and for every factor:

  • Treverse  all the opposite components and discover which factor offers the best GCD amongst them.
  • That may the be subsequent factor as a result of it would generate a better GCD for the B[] array. 

Continuen this course of until the array is constructed.

Comply with 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

C++

  

#embody <bits/stdc++.h>

utilizing namespace std;

  

pair<vector<int>, vector<int> >

Findpermutation(vector<int>& A)

{

    

    

    vector<bool> used(A.dimension(), 0);

  

    

    vector<int> ansA;

    vector<int> ansB;

  

    int x = 0;

  

    for (int i = 0; i < A.dimension(); i++) {

  

        

        

        

        int temp = 0, mx_gcd = 0, index = -1;

  

        

        

        

        for (int j = 0; j < A.dimension(); j++) {

  

            if (!used[j]) {

  

                

                temp = __gcd(x, A[j]);

  

                

                

                if (temp > mx_gcd) {

                    mx_gcd = temp;

                    index = j;

                }

            }

        }

  

        

        

        x = __gcd(x, mx_gcd);

  

        

        used[index] = 1;

  

        

        ansB.push_back(x);

        ansA.push_back(A[index]);

    }

    return { ansA, ansB };

}

  

int primary()

{

    vector<int> A = { 2, 1, 4, 8, 16, 32, 5 };

  

    

    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;

}

Output

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

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

LEAVE A REPLY

Please enter your comment!
Please enter your name here