Find original numbers from gcd ( ) every pair | Java 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 ; reverse array ; Driver code
import java . util . Arrays ; class GFG { static void printArr ( int arr [ ] , int n ) { for ( int i = 0 ; i < n ; i ++ ) { System . out . print ( arr [ i ] + " ▁ " ) ; } } static void findNumbers ( int arr [ ] , int n ) { Arrays . sort ( arr ) ; reverse ( arr ) ; int freq [ ] = new int [ arr [ 0 ] + 1 ] ; for ( int i = 0 ; i < n ; i ++ ) { freq [ arr [ i ] ] ++ ; } int size = ( int ) Math . sqrt ( n ) ; int brr [ ] = new int [ size ] , x , l = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( freq [ arr [ i ] ] > 0 && l < size ) { 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 ) ; } public static void reverse ( int [ ] input ) { int last = input . length - 1 ; int middle = input . length / 2 ; for ( int i = 0 ; i <= middle ; i ++ ) { int temp = input [ i ] ; input [ i ] = input [ last - i ] ; input [ last - i ] = temp ; } } static int __gcd ( int a , int b ) { if ( b == 0 ) { return a ; } return __gcd ( b , a % b ) ; } public static void main ( String [ ] args ) { 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 = arr . length ; findNumbers ( arr , n ) ; } }