Count of triplets in a given Array having GCD K | Java 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 code
class GFG { static int MAXN = 1000001 ; static int freq [ ] = new int [ MAXN ] ; static int mul [ ] = new int [ MAXN ] ; static int cnt [ ] = new int [ MAXN ] ; static int nC3 ( int n ) { if ( n < 3 ) return 0 ; return ( n * ( n - 1 ) * ( n - 2 ) ) / 6 ; } static void count_triplet ( int [ ] arr , int N , int K ) { int i , j ; for ( i = 0 ; i < N ; i ++ ) { freq [ arr [ i ] ] ++ ; } for ( i = 1 ; i <= 1000000 ; i ++ ) { for ( j = i ; j <= 1000000 ; j += i ) { mul [ i ] += freq [ j ] ; } cnt [ i ] = nC3 ( mul [ i ] ) ; } for ( i = 1000000 ; i >= 1 ; i -- ) { for ( j = 2 * i ; j <= 1000000 ; j += i ) { cnt [ i ] -= cnt [ j ] ; } } System . out . print ( " Number ▁ of ▁ triplets ▁ " + " with ▁ GCD ▁ " + K ) ; System . out . print ( " ▁ are ▁ " + cnt [ K ] ) ; } public static void main ( String [ ] args ) { int [ ] arr = { 1 , 7 , 12 , 6 , 15 , 9 } ; int N = 6 , K = 3 ; count_triplet ( arr , N , K ) ; } }