Count of distinct GCDs among all the non | 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 ; Input ; Function calling
function gcd ( a , b ) { if ( b == 0 ) return a ; return gcd ( b , a % b ) ; } function distinctGCDs ( arr , N ) { let M = - 1 , ans = 0 ; var Mp = new Map ( ) ; for ( let i = 0 ; i < N ; i ++ ) { M = Math . max ( M , arr [ i ] ) ; Mp . set ( arr [ i ] , 1 ) ; } for ( let i = 1 ; i <= M ; i ++ ) { let currGcd = 0 ; for ( let j = i ; j <= M ; j += i ) { if ( Mp . has ( j ) ) { currGcd = gcd ( currGcd , j ) ; if ( currGcd == i ) { ans ++ ; break ; } } } } return ans ; } let arr = [ 3 , 11 , 14 , 6 , 12 ] ; let N = arr . length ; document . write ( distinctGCDs ( arr , N ) + ' ' ) ;