Array with GCD of any of its subset belongs to the given array | Java implementation to generate the required array ; Function to return gcd of a and b ; Function to find gcd of array of numbers ; Function to generate the array with required constraints . ; computing GCD of the given set ; Solution exists if GCD of array is equal to the minimum element of the array ; Printing the built array ; Driver Code ; Taking in the input and initializing the set STL set in cpp has a property that it maintains the elements in sorted order , thus we do not need to sort them externally ; Calling the computing function .
import java . io . * ; import java . util . * ; class GFG { static int gcd ( int a , int b ) { if ( a == 0 ) return b ; return gcd ( b % a , a ) ; } public static int findGCD ( ArrayList < Integer > arr , int n ) { int result = arr . get ( 0 ) ; for ( int i = 1 ; i < n ; i ++ ) result = gcd ( arr . get ( i ) , result ) ; return result ; } public static void compute ( ArrayList < Integer > arr , int n ) { ArrayList < Integer > answer = new ArrayList < Integer > ( ) ; int GCD_of_array = findGCD ( arr , n ) ; if ( GCD_of_array == arr . get ( 0 ) ) { answer . add ( arr . get ( 0 ) ) ; for ( int i = 1 ; i < n ; i ++ ) { answer . add ( arr . get ( 0 ) ) ; answer . add ( arr . get ( i ) ) ; } for ( int i = 0 ; i < answer . size ( ) ; i ++ ) System . out . print ( answer . get ( i ) + " ▁ " ) ; } else System . out . print ( " No ▁ array ▁ " + " can ▁ be ▁ build " ) ; } public static void main ( String args [ ] ) { int n = 3 ; Integer input [ ] = { 2 , 5 , 6 , 7 , 11 } ; HashSet < Integer > GCD = new HashSet < Integer > ( Arrays . asList ( input ) ) ; ArrayList < Integer > arr = new ArrayList < Integer > ( ) ; for ( int v : GCD ) arr . add ( v ) ; compute ( arr , n ) ; } }