Count pairs from an array having GCD equal to the minimum element in the pair | Function to count pairs from an array having GCD equal to minimum element of that pair ; Stores the resultant count ; Stores the frequency of each array element ; Traverse the array arr [ ] ; Iterate over the Map mp ; Stores the array element ; Stores the count of array element x ; If x is 1 ; Increment res by N - 1 ; Increment res by yC2 ; Iterate over the range [ 2 , sqrt ( x ) ] ; If x is divisible by j ; Increment the value of res by mp [ j ] ; If j is not equal to x / j ; Increment res by mp [ x / j ] ; Return the resultant count ; Driver Code
function CountPairs ( arr , N ) { var res = 0 ; var mp = new Map ( ) ; for ( var i = 0 ; i < N ; i ++ ) { if ( mp . has ( arr [ i ] ) ) { mp . set ( arr [ i ] , mp . get ( arr [ i ] ) + 1 ) ; } else { mp . set ( arr [ i ] , 1 ) ; } } mp . forEach ( ( value , key ) => { var x = key ; var y = value ; if ( x == 1 ) { res += N - 1 ; } res += parseInt ( ( y * ( y - 1 ) ) / 2 ) ; for ( var j = 2 ; j <= parseInt ( Math . sqrt ( x ) ) ; j ++ ) { if ( x % j == 0 ) { res += mp . get ( j ) ; if ( j != parseInt ( x / j ) ) res += mp . get ( parseInt ( x / j ) ) ; } } } ) ; return res ; } var arr = [ 2 , 3 , 1 , 2 ] ; var N = arr . length ; document . write ( CountPairs ( arr , N ) ) ;