Given an integer array arr[] and an integer K, the task is to count all triplets whose GCD is equal to K.
Examples:
Input: arr[] = {1, 4, 8, 14, 20}, K = 2
Output: 3
Explanation:
Triplets (4, 14, 20), (8, 14, 20) and (4, 8, 14) have GCD equal to 2.
Input: arr[] = {1, 2, 3, 4, 5}, K = 7
Output: 0
Approach:
Follow the steps below to solve the problem:
- Maintain an array cnt[i] which denotes the numbers of triplet in array with GCD = i.
- Now, to find cnt[i], first of all count all the multiples of i in the array which is stored in another array mul[i].
- Now select any three values from mul[i]. Number of ways of selecting three values is mul [i] C 3, store this value in cnt[i].
- But it also includes the triplets with GCD a multiple of i.So we Again iterate over all the multiples of i and subtract cnt[j] from cnt[i] where j is a multiple of i.
- Finally return cnt[K].
Below is the implementation of the above approach:
C++
// C++ program to count the// number of triplets in the// array with GCD equal to K#include <bits/stdc++.h>using namespace std;const int MAXN = 1e6 + 1;// frequency arrayint freq[MAXN] = { 0 };// mul[i] stores the count// of multiples of iint mul[MAXN] = { 0 };// cnt[i] stores the count// of triplets with gcd = iint cnt[MAXN] = { 0 };// Return nC3int nC3(int n){ if (n < 3) return 0; return (n * (n - 1) * (n - 2)) / 6;}// Function to count and return// the number of triplets in the// array with GCD equal to Kvoid count_triplet(vector<int> arr, int N, int K){ for (int i = 0; i < N; i++) { // Store frequency of // array elements freq[arr[i]]++; } for (int i = 1; i <= 1000000; i++) { for (int j = i; j <= 1000000; j += i) { // Store the multiples of // i present in the array mul[i] += freq[j]; } // Count triplets with gcd // equal to any multiple of i cnt[i] = nC3(mul[i]); } // Remove all triplets which have gcd // equal to a multiple of i for (int i = 1000000; i >= 1; i--) { for (int j = 2 * i; j <= 1000000; j += i) { cnt[i] -= cnt[j]; } } cout << "Number of triplets " << "with GCD " << K; cout << " are " << cnt[K];}// Driver Programint main(){ vector<int> arr = { 1, 7, 12, 6, 15, 9 }; int N = 6, K = 3; count_triplet(arr, N, K); return 0;} |
Java
// Java program to count the// number of triplets in the// array with GCD equal to Kclass GFG{ static int MAXN = 1000001;// Frequency arraystatic int freq[] = new int[MAXN];// mul[i] stores the count// of multiples of istatic int mul[] = new int[MAXN];// cnt[i] stores the count// of triplets with gcd = istatic int cnt[] = new int[MAXN];// Return nC3static int nC3(int n){ if (n < 3) return 0; return (n * (n - 1) * (n - 2)) / 6;}// Function to count and return// the number of triplets in the// array with GCD equal to Kstatic void count_triplet(int[] arr, int N, int K){ int i, j; for(i = 0; i < N; i++) { // Store frequency of // array elements freq[arr[i]]++; } for(i = 1; i <= 1000000; i++) { for(j = i; j <= 1000000; j += i) { // Store the multiples of // i present in the array mul[i] += freq[j]; } // Count triplets with gcd // equal to any multiple of i cnt[i] = nC3(mul[i]); } // Remove all triplets which have gcd // equal to a multiple of 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]);}// Driver codepublic static void main (String []args){ int []arr = { 1, 7, 12, 6, 15, 9 }; int N = 6, K = 3; count_triplet(arr, N, K);} }// This code is contributed by chitranayal |
Python3
# Python3 program to count the number of # triplets in the array with GCD equal to K MAXN = int(1e6 + 1)# Frequency arrayfreq = [0] * MAXN# mul[i] stores the count# of multiples of imul = [0] * MAXN# cnt[i] stores the count# of triplets with gcd = icnt = [0] * MAXN# Return nC3def nC3(n): if(n < 3): return 0 return (n * (n - 1) * (n - 2)) / 6# Function to count and return# the number of triplets in the# array with GCD equal to Kdef count_triplet(arr, N, K): for i in range(N): # Store frequency of # array elements freq[arr[i]] += 1 for i in range(1, 1000000 + 1): for j in range(i, 1000000 + 1, i): # Store the multiples of # i present in the array mul[i] += freq[j] # Count triplets with gcd # equal to any multiple of i cnt[i] = nC3(mul[i]) # Remove all triplets which have gcd # equal to a multiple of i for i in range(1000000, 0, -1): for j in range(2 * i, 1000000 + 1, i): cnt[i] -= cnt[j] print("Number of triplets with GCD" " {0} are {1}".format(K, int(cnt[K])))# Driver Codeif __name__ == '__main__': arr = [ 1, 7, 12, 6, 15, 9 ] N = 6 K = 3 count_triplet(arr, N, K)# This code is contributed by Shivam Singh |
C#
// C# program to count the// number of triplets in the// array with GCD equal to Kusing System;class GFG{ static int MAXN = 1000001; // Frequency arraystatic int []freq = new int[MAXN]; // mul[i] stores the count// of multiples of istatic int []mul = new int[MAXN]; // cnt[i] stores the count// of triplets with gcd = istatic int []cnt = new int[MAXN]; // Return nC3static int nC3(int n){ if (n < 3) return 0; return (n * (n - 1) * (n - 2)) / 6;} // Function to count and return// the number of triplets in the// array with GCD equal to Kstatic void count_triplet(int[] arr, int N, int K){ int i, j; for(i = 0; i < N; i++) { // Store frequency of // array elements freq[arr[i]]++; } for(i = 1; i <= 1000000; i++) { for(j = i; j <= 1000000; j += i) { // Store the multiples of // i present in the array mul[i] += freq[j]; } // Count triplets with gcd // equal to any multiple of i cnt[i] = nC3(mul[i]); } // Remove all triplets which have gcd // equal to a multiple of i for(i = 1000000; i >= 1; i--) { for(j = 2 * i; j <= 1000000; j += i) { cnt[i] -= cnt[j]; } } Console.Write("Number of triplets " + "with GCD " + K); Console.Write(" are " + cnt[K]);} // Driver codepublic static void Main (string []args){ int []arr = { 1, 7, 12, 6, 15, 9 }; int N = 6, K = 3; count_triplet(arr, N, K);} } // This code is contributed by Ritik Bansal |
Javascript
<script>// Javascript program to count the// number of triplets in the// array with GCD equal to Kvar MAXN = 1000001;// frequency arrayvar freq = Array(MAXN).fill(0);// mul[i] stores the count// of multiples of ivar mul = Array(MAXN).fill(0);// cnt[i] stores the count// of triplets with gcd = ivar cnt = Array(MAXN).fill(0);// Return nC3function nC3(n){ if (n < 3) return 0; return (n * (n - 1) * (n - 2)) / 6;}// Function to count and return// the number of triplets in the// array with GCD equal to Kfunction count_triplet(arr, N, K){ for (var i = 0; i < N; i++) { // Store frequency of // array elements freq[arr[i]]++; } for (var i = 1; i <= 1000000; i++) { for (var j = i; j <= 1000000; j += i) { // Store the multiples of // i present in the array mul[i] += freq[j]; } // Count triplets with gcd // equal to any multiple of i cnt[i] = nC3(mul[i]); } // Remove all triplets which have gcd // equal to a multiple of i for (var i = 1000000; i >= 1; i--) { for (var j = 2 * i; j <= 1000000; j += i) { cnt[i] -= cnt[j]; } } document.write( "Number of triplets " + "with GCD " + K); document.write( " are " + cnt[K]);}// Driver Programvar arr = [ 1, 7, 12, 6, 15, 9 ];var N = 6, K = 3;count_triplet(arr, N, K);</script> |
Output:
Number of triplets with GCD 3 are 4
Time Complexity: O (N * log N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
