Longest subsequence having maximum GCD between any pair of distinct elements | Java program for the above approach ; Recursive function to return gcd of a and b ; Function to find GCD of pair with maximum GCD ; Stores maximum element of arr [ ] ; Find the maximum element ; Maintain a count array ; Store the frequency of arr [ ] ; Stores the multiples of a number ; Iterate over the range [ MAX , 1 ] ; Iterate from current potential GCD till it is less than MAX ; A multiple found ; Increment potential GCD by itself io check i , 2 i , 3 i ... ; If 2 multiples found max GCD found ; Function to find longest subsequence such that GCD of any two distinct integers is maximum ; Base Cases ; Compare current GCD to the maximum GCD ; If true increment and move the pointer ; Return max of either subsequences ; Driver Code ; Sorted array ; Function call to calculate GCD of pair with maximum GCD ; Print the result
import java . util . * ; class GFG { static int __gcd ( int a , int b ) { return b == 0 ? a : __gcd ( b , a % b ) ; } static int findMaxGCD ( int arr [ ] , int N ) { int high = 0 ; for ( int i = 0 ; i < N ; i ++ ) { high = Math . max ( high , arr [ i ] ) ; } int [ ] count = new int [ high + 1 ] ; for ( int i = 0 ; i < N ; i ++ ) { count [ arr [ i ] ] += 1 ; } int counter = 0 ; for ( int i = high ; i > 0 ; i -- ) { int j = i ; while ( j <= high ) { if ( count [ j ] > 0 ) counter += count [ j ] ; j += i ; if ( counter == 2 ) return i ; } counter = 0 ; } return 0 ; } static int maxlen ( int i , int j , int arr [ ] , int arr1 [ ] , int N , int maxgcd ) { int a = 1 ; if ( i >= N j >= N ) return 0 ; if ( __gcd ( arr [ i ] , arr1 [ j ] ) == maxgcd && arr [ i ] != arr1 [ j ] ) { a = Math . max ( a , 1 + maxlen ( i , j + 1 , arr , arr1 , N , maxgcd ) ) ; return a ; } return Math . max ( maxlen ( i + 1 , j , arr , arr1 , N , maxgcd ) , maxlen ( i , j + 1 , arr , arr1 , N , maxgcd ) ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 2 , 8 , 5 , 6 } ; int arr1 [ ] = { 1 , 2 , 8 , 5 , 6 } ; int n = arr . length ; Arrays . sort ( arr ) ; int maxgcd = findMaxGCD ( arr , n ) ; System . out . print ( maxlen ( 0 , 0 , arr , arr1 , n , maxgcd ) ) ; } }