Array with GCD of any of its subset belongs to the given array | C ++ 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 function ; 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 .
#include <bits/stdc++.h> NEW_LINE using namespace std ; int gcd ( int a , int b ) { if ( a == 0 ) return b ; return gcd ( b % a , a ) ; } int findGCD ( vector < int > arr , int n ) { int result = arr [ 0 ] ; for ( int i = 1 ; i < n ; i ++ ) result = gcd ( arr [ i ] , result ) ; return result ; } void compute ( vector < int > arr , int n ) { vector < int > answer ; int GCD_of_array = findGCD ( arr , n ) ; if ( GCD_of_array == arr [ 0 ] ) { answer . push_back ( arr [ 0 ] ) ; for ( int i = 1 ; i < n ; i ++ ) { answer . push_back ( arr [ 0 ] ) ; answer . push_back ( arr [ i ] ) ; } for ( int i = 0 ; i < answer . size ( ) ; i ++ ) cout << answer [ i ] << " ▁ " ; } else cout << " No ▁ array ▁ can ▁ be ▁ build " ; } int main ( ) { int n = 3 ; int input [ ] = { 2 , 5 , 6 , 7 , 11 } ; set < int > GCD ( input , input + n ) ; vector < int > arr ; set < int > :: iterator it ; for ( it = GCD . begin ( ) ; it != GCD . end ( ) ; ++ it ) arr . push_back ( * it ) ; compute ( arr , n ) ; return 0 ; }