Count of triplets in a given Array having GCD K | Javascript program to count the number of triplets in the array with GCD equal to K ; frequency array ; mul [ i ] stores the count of multiples of i ; cnt [ i ] stores the count of triplets with gcd = i ; Return nC3 ; Function to count and return the number of triplets in the array with GCD equal to K ; Store frequency of array elements ; Store the multiples of i present in the array ; Count triplets with gcd equal to any multiple of i ; Remove all triplets which have gcd equal to a multiple of i ; Driver Program
var MAXN = 1000001 ; var freq = Array ( MAXN ) . fill ( 0 ) ; var mul = Array ( MAXN ) . fill ( 0 ) ; var cnt = Array ( MAXN ) . fill ( 0 ) ; function nC3 ( n ) { if ( n < 3 ) return 0 ; return ( n * ( n - 1 ) * ( n - 2 ) ) / 6 ; } function count_triplet ( arr , N , K ) { for ( var i = 0 ; i < N ; i ++ ) { freq [ arr [ i ] ] ++ ; } for ( var i = 1 ; i <= 1000000 ; i ++ ) { for ( var j = i ; j <= 1000000 ; j += i ) { mul [ i ] += freq [ j ] ; } cnt [ i ] = nC3 ( mul [ i ] ) ; } for ( var i = 1000000 ; i >= 1 ; i -- ) { for ( var j = 2 * i ; j <= 1000000 ; j += i ) { cnt [ i ] -= cnt [ j ] ; } } document . write ( " " + " " + K ) ; document . write ( " " + cnt [ K ] ) ; } var arr = [ 1 , 7 , 12 , 6 , 15 , 9 ] ; var N = 6 , K = 3 ; count_triplet ( arr , N , K ) ;