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