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
using System ; using System . Collections . Generic ; class GFG { static int GCD ( int a , int b ) { if ( b == 0 ) return a ; return GCD ( b , a % b ) ; } static int GCDArr ( List < int > a ) { int ans = a [ 0 ] ; foreach ( int val in a ) { ans = GCD ( ans , val ) ; } return ans ; } static bool findSubseqUtil ( int [ ] a , int [ ] b , List < int > ans , int k , int i , int N ) { if ( ans . Count == N ) { if ( GCDArr ( ans ) == k ) { foreach ( int val in ans ) Console . Write ( val + " ▁ " ) ; return true ; } else { return false ; } } if ( a [ i ] % k == 0 ) { ans . Add ( a [ i ] ) ; bool temp = findSubseqUtil ( a , b , ans , k , i + 1 , N ) ; if ( temp == true ) return true ; ans . RemoveAt ( ans . Count - 1 ) ; } if ( b [ i ] % k == 0 ) { ans . Add ( b [ i ] ) ; bool temp = findSubseqUtil ( a , b , ans , k , i + 1 , N ) ; if ( temp == true ) return true ; ans . RemoveAt ( ans . Count - 1 ) ; } return false ; } static void findSubseq ( int [ ] A , int [ ] B , int K , int i , int N ) { List < int > ans = new List < int > ( ) ; bool ret = findSubseqUtil ( A , B , ans , K , i , N ) ; if ( ret == false ) Console . Write ( - 1 ) ; } public static void Main ( ) { int [ ] A = { 5 , 3 , 6 , 2 , 9 } ; int [ ] B = { 21 , 7 , 14 , 12 , 28 } ; int N = A . Length ; int K = 3 ; findSubseq ( A , B , K , 0 , N ) ; } }