Find original numbers from gcd ( ) every pair | C ++ implementation of the approach ; Utility function to print the contents of an array ; Function to find the required numbers ; Sort array in decreasing order ; Count frequency of each element ; Size of the resultant array ; Store the highest element in the resultant array ; Decrement the frequency of that element ; Compute GCD ; Decrement GCD value by 2 ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void printArr ( int arr [ ] , int n ) { for ( int i = 0 ; i < n ; i ++ ) cout << arr [ i ] << " ▁ " ; } void findNumbers ( int arr [ ] , int n ) { sort ( arr , arr + n , greater < int > ( ) ) ; int freq [ arr [ 0 ] + 1 ] = { 0 } ; for ( int i = 0 ; i < n ; i ++ ) freq [ arr [ i ] ] ++ ; int size = sqrt ( n ) ; int brr [ size ] = { 0 } , x , l = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( freq [ arr [ i ] ] > 0 ) { brr [ l ] = arr [ i ] ; freq [ brr [ l ] ] -- ; l ++ ; for ( int j = 0 ; j < l ; j ++ ) { if ( i != j ) { x = __gcd ( arr [ i ] , brr [ j ] ) ; freq [ x ] -= 2 ; } } } } printArr ( brr , size ) ; } int main ( ) { int arr [ ] = { 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 5 , 5 , 5 , 7 , 10 , 12 , 2 , 2 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; findNumbers ( arr , n ) ; return 0 ; }