Generate an N | Java 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 ; Given value of K ; Function call to generate a subsequence whose GCD is K
import java . io . * ; import java . lang . * ; import java . util . * ; class GFG { static int GCD ( int a , int b ) { if ( b == 0 ) return a ; return GCD ( b , a % b ) ; } static int GCDArr ( ArrayList < Integer > a ) { int ans = a . get ( 0 ) ; for ( int val : a ) { ans = GCD ( ans , val ) ; } return ans ; } static boolean findSubseqUtil ( int a [ ] , int b [ ] , ArrayList < Integer > ans , int k , int i ) { if ( ans . size ( ) == a . length ) { if ( GCDArr ( ans ) == k ) { System . out . println ( ans ) ; return true ; } else { return false ; } } if ( a [ i ] % k == 0 ) { ans . add ( a [ i ] ) ; boolean temp = findSubseqUtil ( a , b , ans , k , i + 1 ) ; if ( temp == true ) return true ; ans . remove ( ans . size ( ) - 1 ) ; } if ( b [ i ] % k == 0 ) { ans . add ( b [ i ] ) ; boolean temp = findSubseqUtil ( a , b , ans , k , i + 1 ) ; if ( temp == true ) return true ; ans . remove ( ans . size ( ) - 1 ) ; } return false ; } static void findSubseq ( int A [ ] , int B [ ] , int K , int i ) { ArrayList < Integer > ans = new ArrayList < > ( ) ; boolean ret = findSubseqUtil ( A , B , ans , K , i ) ; if ( ret == false ) System . out . println ( - 1 ) ; } public static void main ( String [ ] args ) { int A [ ] = { 5 , 3 , 6 , 2 , 9 } ; int B [ ] = { 21 , 7 , 14 , 12 , 28 } ; int K = 3 ; findSubseq ( A , B , K , 0 ) ; } }