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