Generate an N | 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 ; Given arrays ; Given value of K ; Function call to generate the required subsequence
def GCD ( a , b ) : NEW_LINE INDENT if not b : NEW_LINE INDENT return a NEW_LINE DEDENT return GCD ( b , a % b ) NEW_LINE DEDENT def GCDArr ( a ) : NEW_LINE INDENT ans = a [ 0 ] NEW_LINE for i in a : NEW_LINE INDENT ans = GCD ( ans , i ) NEW_LINE DEDENT return ans NEW_LINE DEDENT def findSubseqUtil ( a , b , ans , k , i ) : NEW_LINE INDENT if len ( ans ) == len ( a ) : NEW_LINE INDENT if GCDArr ( ans ) == k : NEW_LINE INDENT print ( ans ) NEW_LINE return True NEW_LINE DEDENT else : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT ans . append ( a [ i ] ) NEW_LINE temp = findSubseqUtil ( a , b , ans , k , i + 1 ) NEW_LINE if temp == True : NEW_LINE INDENT return True NEW_LINE DEDENT ans . pop ( ) NEW_LINE ans . append ( b [ i ] ) NEW_LINE temp = findSubseqUtil ( a , b , ans , k , i + 1 ) NEW_LINE if temp == True : NEW_LINE INDENT return True NEW_LINE DEDENT ans . pop ( ) NEW_LINE DEDENT def findSubseq ( A , B , K , i ) : NEW_LINE INDENT ans = [ ] NEW_LINE findSubseqUtil ( A , B , ans , K , i ) NEW_LINE if not ans : NEW_LINE INDENT print ( - 1 ) NEW_LINE DEDENT DEDENT A = [ 5 , 3 , 6 , 2 , 9 ] NEW_LINE B = [ 21 , 7 , 14 , 12 , 28 ] NEW_LINE K = 3 NEW_LINE ans = findSubseq ( A , B , K , 0 ) NEW_LINE