Generate an N | C ++ program for the above approach ; Function to calculate GCD of given array ; Utility function to check for all the combinations ; If a sequence of size N is obtained ; If gcd of current combination is K ; If current element from first array is divisible by K ; Recursively proceed further ; If current combination satisfies given condition ; Remove the element from the combination ; If current element from second array is divisible by K ; Recursively proceed further ; If current combination satisfies given condition ; Remove the element from the combination ; Function to check for all possible combinations ; Stores the subsequence ; If GCD of any sequence is not equal to K ; Driver Code ; Given arrays ; size of the array ; Given value of K ; Function call to generate a subsequence whose GCD is K
#include <bits/stdc++.h> NEW_LINE using namespace std ; int GCD ( int a , int b ) { if ( b == 0 ) return a ; return GCD ( b , a % b ) ; } int GCDArr ( vector < int > a ) { int ans = a [ 0 ] ; for ( auto val : a ) { ans = GCD ( ans , val ) ; } return ans ; } bool findSubseqUtil ( int a [ ] , int b [ ] , vector < int > ans , int k , int i , int N ) { if ( ans . size ( ) == N ) { if ( GCDArr ( ans ) == k ) { for ( auto val : ans ) cout << val << " ▁ " ; return true ; } else { return false ; } } if ( a [ i ] % k == 0 ) { ans . push_back ( a [ i ] ) ; bool temp = findSubseqUtil ( a , b , ans , k , i + 1 , N ) ; if ( temp == true ) return true ; ans . pop_back ( ) ; } if ( b [ i ] % k == 0 ) { ans . push_back ( b [ i ] ) ; bool temp = findSubseqUtil ( a , b , ans , k , i + 1 , N ) ; if ( temp == true ) return true ; ans . pop_back ( ) ; } return false ; } void findSubseq ( int A [ ] , int B [ ] , int K , int i , int N ) { vector < int > ans ; bool ret = findSubseqUtil ( A , B , ans , K , i , N ) ; if ( ret == false ) cout << -1 << " STRNEWLINE " ; } int main ( ) { int A [ ] = { 5 , 3 , 6 , 2 , 9 } ; int B [ ] = { 21 , 7 , 14 , 12 , 28 } ; int N = sizeof ( A ) / sizeof ( A [ 0 ] ) ; int K = 3 ; findSubseq ( A , B , K , 0 , N ) ; return 0 ; }