Count of distinct GCDs among all the non | Java program for the above approach ; Function to calculate gcd ; Function to calculate the number of distinct GCDs among all non - empty subsequences of an array ; Variables to store the largest element in array and the required count ; Map to store whether a number is present in A ; Calculate largest number in A and mapping A to Mp ; Iterate over all possible values of GCD ; Variable to check current GCD ; Iterate over all multiples of i ; If j is present in A ; Calculate gcd of all encountered multiples of i ; Current GCD is possible ; Return answer ; Driver code ; Input ; Function calling
import java . util . * ; class GFG { static int gcd ( int a , int b ) { return b == 0 ? a : gcd ( b , a % b ) ; } static int distinctGCDs ( int [ ] arr , int N ) { int M = - 1 , ans = 0 ; HashMap < Integer , Integer > Mp = new HashMap < Integer , Integer > ( ) ; for ( int i = 0 ; i < N ; i ++ ) { M = Math . max ( M , arr [ i ] ) ; if ( Mp . containsKey ( arr [ i ] ) ) Mp . put ( arr [ i ] , 1 ) ; else Mp . put ( arr [ i ] , 0 ) ; } for ( int i = 1 ; i <= M ; i ++ ) { int currGcd = 0 ; for ( int j = i ; j <= M ; j += i ) { if ( Mp . containsKey ( j ) ) { currGcd = gcd ( currGcd , j ) ; if ( currGcd == i ) { ans ++ ; break ; } } } } return ans ; } public static void main ( String [ ] args ) { int [ ] arr = { 3 , 11 , 14 , 6 , 12 } ; int N = arr . length ; System . out . println ( distinctGCDs ( arr , N ) ) ; } }