Smallest subsequence having GCD equal to GCD of given array | Java program to implement the above approach ; Function to calculate gcd of two numbers ; Function to print the smallest subsequence that satisfies the condition ; Stores gcd of the array . ; Traverse the given array ; Update gcdArr ; Traverse the given array . ; If current element equal to gcd of array . ; Generate all possible pairs . ; If gcd of current pair equal to gcdArr ; Print current pair of the array ; Driver Code
import java . io . * ; class GFG { static int gcd ( int a , int b ) { if ( b == 0 ) return a ; return gcd ( b , a % b ) ; } static void printSmallSub ( int [ ] arr , int N ) { int gcdArr = 0 ; for ( int i = 0 ; i < N ; i ++ ) { gcdArr = gcd ( gcdArr , arr [ i ] ) ; } for ( int i = 0 ; i < N ; i ++ ) { if ( arr [ i ] == gcdArr ) { System . out . print ( arr [ i ] + " ▁ " ) ; return ; } } for ( int i = 0 ; i < N ; i ++ ) { for ( int j = i + 1 ; j < N ; j ++ ) { if ( gcd ( arr [ i ] , arr [ j ] ) == gcdArr ) { System . out . print ( arr [ i ] + " ▁ " + arr [ j ] ) ; return ; } } } } public static void main ( String [ ] args ) { int arr [ ] = { 4 , 6 , 12 } ; int N = arr . length ; printSmallSub ( arr , N ) ; } }