Given an array A[] and positive integer K, the task is to count the total number of pairs in the array whose product is divisible by K.
Examples :
Input: A[] = [1, 2, 3, 4, 5], K = 2
Output: 7
Explanation: The 7 pairs of indices whose corresponding products are divisible by 2 are
(0, 1), (0, 3), (1, 2), (1, 3), (1, 4), (2, 3), and (3, 4).
Other pairs such as (0, 2) and (2, 4) have products 3 and 15 respectively, which are not divisible by 2.Input: A[] = [1, 2, 3, 4], K = 5
Output: 0
Explanation: There does not exist any pair of indices whose corresponding product is divisible by 5.
Naive approach: For finding the counts of all pairs we can simply do a nested loop iteration and for each of element we can check all remaining elements whether their product is divisible by given key or not.
Algorithm:
- Initialize a counter variable count to 0.
- Loop i from 0 to N-1
- Loop j from i+1 to N-1
i. If A[i]*A[j] is divisible by K, then increment count by 1.
- Loop j from i+1 to N-1
- Return count as the final result.
Below is the implementation of the approach:
C++
// C++ code for the approach#include <bits/stdc++.h>using namespace std;// Function to count the number of pairs in the array// whose product is divisible by Kint countPairs(int arr[], int n, int k){ int count = 0; // Loop to iterate through all pairs of elements in the array for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // Check if the product of elements is divisible by K if ((arr[i] * arr[j]) % k == 0) { count++; } } } return count;}// Driver codeint main(){ int arr[] = { 1, 2, 3, 4, 5 }; int n = sizeof(arr) / sizeof(arr[0]); int k = 2; // Call the function to count the number of pairs int count = countPairs(arr, n, k); // Print the count of pairs cout << count << endl; return 0;} |
Java
import java.util.*;public class Main { // Function to count the number of pairs in the array // whose product is divisible by K static int countPairs(int[] arr, int n, int k) { int count = 0; // Loop to iterate through all pairs of elements in the array for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // Check if the product of elements is divisible by K if ((arr[i] * arr[j]) % k == 0) { count++; } } } return count; } // Driver code public static void main(String[] args) { int[] arr = { 1, 2, 3, 4, 5 }; int n = arr.length; int k = 2; // Call the function to count the number of pairs int count = countPairs(arr, n, k); // Print the count of pairs System.out.println(count); }} |
Python3
# Function to count the number of pairs in the list# whose product is divisible by kdef countPairs(arr, k): count = 0 # Loop to iterate through all pairs of elements in the list for i in range(len(arr)): for j in range(i + 1, len(arr)): # Check if the product of elements is divisible by k if (arr[i] * arr[j]) % k == 0: count += 1 return count# Driver codearr = [1, 2, 3, 4, 5]k = 2# Call the function to count the number of pairscount = countPairs(arr, k)# Print the count of pairsprint(count) |
C#
using System;class Program{ // Function to count the number of pairs in the array // whose product is divisible by K static int CountPairs(int[] arr, int n, int k) { int count = 0; // Loop to iterate through all pairs of elements in the array for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // Check if the product of elements is divisible by K if ((arr[i] * arr[j]) % k == 0) { count++; } } } return count; } // Main method static void Main() { int[] arr = { 1, 2, 3, 4, 5 }; int n = arr.Length; int k = 2; // Call the function to count the number of pairs int count = CountPairs(arr, n, k); // Print the count of pairs Console.WriteLine(count); }} |
Javascript
// Function to count the number of pairs in the array// whose product is divisible by Kfunction countPairs(arr, k) { let count = 0; // Loop to iterate through all pairs of elements in the array for (let i = 0; i < arr.length; i++) { for (let j = i + 1; j < arr.length; j++) { // Check if the product of elements is divisible by K if ((arr[i] * arr[j]) % k === 0) { count++; } } } return count;}// Driver codelet arr = [1, 2, 3, 4, 5];let k = 2;// Call the function to count the number of pairslet count = countPairs(arr, k);// Print the count of pairsconsole.log(count); |
Output
7
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient approach: The problem can be solved efficiently using hashing based on the following observation:
- For checking the divisibility of product with K, better to deal with the GCD of number with K. This will remove all other factors from consideration. As, the number of divisors of K, would be very small when compared with the length of original array size.
- If GCD(a, K) * GCD(b, K) is divisible by key, then a * b should also be divisible by key.
Follow the steps mentioned below to solve the problem:
- Create a map which will store the GCD(A[i], K) as key and its occurrence as value.
- For each element of the array, check all elements of map, whether map’s element is divisible by X (X = quotient when K is divide by GCD(A[i], K))
- if yes add the occurrence of that element from map to answer.
- Also, keep incrementing the occurrence for each element’s GCD with key.
- Return the final count.
Below is the implementation of the above approach
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Program to count pairs whose product// is divisible by keylong long countPairs(vector<int>& A, int key){ long long ans = 0; unordered_map<int, int> mp; for (auto ele : A) { // Calculate gcd of nums[i] and // key long long gcd = __gcd(key, ele); long long x = key / gcd; // Iterate over all possible gcds for (auto it : mp) if (it.first % x == 0) // Add count to answer ans += it.second; // Add gcd to map mp[gcd]++; } return ans;}// Driver codeint main(){ vector<int> A = { 1, 2, 3, 4, 5 }; int key = 2; cout << countPairs(A, key) << endl; return 0;} |
Java
// JAVA program for the above approachimport java.util.*;class GFG { public static int agcd(int a, int b) { if (b == 0) return a; return agcd(b, a % b); } // Program to count pairs whose product // is divisible by key public static long countPairs(int[] A, int key) { long ans = 0; HashMap<Long, Integer> mp = new HashMap<>(); for (int i = 0; i < A.length; ++i) { // Calculate gcd of nums[i] and // key long gcd = agcd(key, A[i]); long x = key / gcd; // Iterate over all possible gcds for (Map.Entry<Long, Integer> it : mp.entrySet()) if (it.getKey() % x == 0) // Add count to answer ans += it.getValue(); // Add gcd to map if (mp.containsKey(gcd)) { mp.put(gcd, mp.get(gcd) + 1); } else { mp.put(gcd, 1); } // mp[gcd]++; } return ans; } // Driver code public static void main(String[] args) { int A[] = new int[] { 1, 2, 3, 4, 5 }; int key = 2; System.out.println(countPairs(A, key)); }}// This code is contributed by Taranpreet |
Python3
# Python3 Program to count pairs whose product# is divisible by keyimport mathdef countPairs(A,key): ans = 0 mp = {} for ele in A: # Calculate gcd of nums[i] and # key gcd = math.gcd(ele, key) x = key // gcd # Iterate over all possible gcds for Key,value in mp.items(): if (Key % x == 0): # Add count to answer ans += value # Add gcd to map if(gcd in mp): mp[gcd] = mp[gcd] + 1 else: mp[gcd] = 1 return ans# Driver codeA = [ 1, 2, 3, 4, 5 ]key = 2print(countPairs(A, key))# This code is contributed by shinjanpatra |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG { static int agcd(int a, int b) { if (b == 0) return a; return agcd(b, a % b); } // Program to count pairs whose product // is divisible by key static long countPairs(int[] A, int key) { long ans = 0; Dictionary<long, int> mp = new Dictionary<long, int>(); for (int i = 0; i < A.Length; ++i) { // Calculate gcd of nums[i] and // key long gcd = agcd(key, A[i]); long x = key / gcd; // Iterate over all possible gcds foreach(KeyValuePair<long, int> it in mp) { if (it.Key % x == 0) // Add count to answer ans += it.Value; } // Add gcd to map if (mp.ContainsKey(gcd)) { mp[gcd] = mp[gcd] + 1; } else { mp.Add(gcd, 1); } // mp[gcd]++; } return ans; } // Driver code public static void Main() { int[] A = { 1, 2, 3, 4, 5 }; int key = 2; Console.WriteLine(countPairs(A, key)); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script>// Program to count pairs whose product// is divisible by keyfunction _gcd(x,y){ if(!y)return x; return _gcd(y,x%y);}function countPairs(A,key){ let ans = 0 let mp = new Map() for(let ele of A){ // Calculate gcd of nums[i] and // key let gcd = _gcd(ele,key) let x = Math.floor(key / gcd) // Iterate over all possible gcds for(let [Key,value] of mp){ if (Key % x == 0) // Add count to answer ans += value } // Add gcd to map if(mp.has(gcd)) mp.set(gcd,mp.get(gcd)+1) else mp.set(gcd,1) } return ans}// Driver codelet A = [ 1, 2, 3, 4, 5 ]let key = 2document.write(countPairs(A, key))// code is contributed by shinjanpatra</script> |
Output
7
Time Complexity: O(N*K1/2)
Space Complexity: O(K1/2)
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!
