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