Find original numbers from gcd() every pair in C++

Concept

With respect of a given array array[] containing GCD of every possible pair of elements of another array, our task is to determine the original numbers which are used to compute the GCD array.

Input

array[] = {6, 1, 1, 13}

Output

13 6 gcd(13, 13) = 13 gcd(13, 6) = 1 gcd(6, 13) = 1 gcd(6, 6) = 6

Input

arr[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 6, 6, 6, 8, 11, 13, 3, 3}

Output

13 11 8 6 6

Method

• At first, sort the array in decreasing order.

• Largest element will always be one of the original numbers. Maintain that number and delete it from the array.

• Calculate GCD of the element taken in the previous step with the current element beginning from the largest and discard the GCD value from the given array.

Example

 Live Demo

// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Shows utility function to print // the contents of an array void printArr(int array[], int n1){    for (int i = 0; i < n1; i++)       cout << array[i] << " "; } // Shows function to determine the required numbers void findNumbers(int array[], int n1){    // Used to sort array in decreasing order    sort(array, array + n1, greater<int>());    int freq1[array[0] + 1] = { 0 };    // Here, count frequency of each element    for (int i = 0; i < n1; i++)       freq1[array[i]]++;    // Shows size of the resultant array    int size1 = sqrt(n1);    int brr1[size1] = { 0 }, x1, l1 = 0;    for (int i = 0; i < n1; i++) {       if (freq1[array[i]] > 0) {          // Here, store the highest element in          // the resultant array          brr1[l1] = array[i];          //Used to decrement the frequency of that element          freq1[brr1[l1]]--;          l1++;          for (int j = 0; j < l1; j++) {             if (i != j) {                // Calculate GCD                x1 = __gcd(array[i], brr1[j]);                // Decrement GCD value by 2                freq1[x1] -= 2;             }          }       }    }    printArr(brr1, size1); } // Driver code int main(){    /* int array[] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1, 6, 6, 6, 8, 11, 13, 3, 3}; */    int array[] = { 6, 1, 1, 13};    int n1 = sizeof(array) / sizeof(array[0]);    findNumbers(array, n1);    return 0; }

Output

13 6