Given an array arr[] consisting of N integers, the task is to find the number of pairs such that the GCD of any pair of array elements is the minimum element of that pair.
Examples:
Input: arr[ ] = {2, 3, 1, 2}
Output: 4
Explanation:
Below are the all possible pairs from the given array:
- (0, 1): The GCD of the pair formed by element at indices 0 and 2 is gcd(2, 1) = 1, which is equal to its minimum value of the pair {2, 1}.
- (0, 3): The GCD of the pair formed by element at indices 0 and 3 is gcd(2, 2) = 2, which is equal to its minimum value of the pair {2, 2}.
- (1, 2): The GCD of the pair formed by taking element at indices 1 and 2 is gcd(3, 1) = 1, which is equal to its minimum value of the pair {3, 1}.
- (2, 3): The GCD of the pair formed by taking element at indices 2 and 3 is gcd(1, 2) = 1, which is equal to its minimum value of the pair {1, 2}.
Therefore, there is a total of 4 possible pairs whose GCD is equal to their minimum element of the pair.
Input: arr[] = {4, 6}
Output: 0
Naive Approach: The simplest approach to solve the given problem is to generate all possible pairs from the given array and if there exists any pair whose GCD is equal to the minimum elements of that pair, then count that pair. After checking for all the pairs, print the value of count obtained as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count pairs from an// array having GCD equal to// minimum element of that pairint countPairs(int arr[], int N){ // Stores the resultant count int count = 0; // Iterate over the range [0, N - 2] for (int i = 0; i < N - 1; i++) { // Iterate over the range [i + 1, N] for (int j = i + 1; j < N; j++) { // If arr[i] % arr[j] is 0 // or arr[j] % arr[i] is 0 if (arr[i] % arr[j] == 0 || arr[j] % arr[i] == 0) { // Increment count by 1 count++; } } } // Return the resultant count return count;}// Driver Codeint main(){ int arr[] = { 2, 3, 1, 2 }; int N = sizeof(arr) / sizeof(arr[0]); cout << countPairs(arr, N); return 0;} |
Java
// java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;public class GFG { // Function to count pairs from an // array having GCD equal to // minimum element of that pair static int countPairs(int arr[], int N) { // Stores the resultant count int count = 0; // Iterate over the range [0, N - 2] for (int i = 0; i < N - 1; i++) { // Iterate over the range [i + 1, N] for (int j = i + 1; j < N; j++) { // If arr[i] % arr[j] is 0 // or arr[j] % arr[i] is 0 if (arr[i] % arr[j] == 0 || arr[j] % arr[i] == 0) { // Increment count by 1 count++; } } } // Return the resultant count return count; } // Driver Code public static void main(String[] args) { int arr[] = { 2, 3, 1, 2 }; int N = arr.length; System.out.print(countPairs(arr, N)); }}// This code is contributed by Kingash. |
Python3
# Python3 program for the above approach# Function to count pairs from an# array having GCD equal to# minimum element of that pairdef countPairs(arr, N): # Stores the resultant count count = 0 # Iterate over the range [0, N - 2] for i in range(N - 1): # Iterate over the range [i + 1, N] for j in range(i + 1, N): # If arr[i] % arr[j] is 0 # or arr[j] % arr[i] is 0 if (arr[i] % arr[j] == 0 or arr[j] % arr[i] == 0): # Increment count by 1 count += 1 # Return the resultant count return count# Driver Codeif __name__ == '__main__': arr = [2, 3, 1, 2] N = len(arr) print (countPairs(arr, N))# This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;public class GFG { // Function to count pairs from an // array having GCD equal to // minimum element of that pair static int countPairs(int[] arr, int N) { // Stores the resultant count int count = 0; // Iterate over the range [0, N - 2] for (int i = 0; i < N - 1; i++) { // Iterate over the range [i + 1, N] for (int j = i + 1; j < N; j++) { // If arr[i] % arr[j] is 0 // or arr[j] % arr[i] is 0 if (arr[i] % arr[j] == 0 || arr[j] % arr[i] == 0) { // Increment count by 1 count++; } } } // Return the resultant count return count; } // Driver Code public static void Main(string[] args) { int[] arr = { 2, 3, 1, 2 }; int N = arr.Length; Console.WriteLine(countPairs(arr, N)); }}// This code is contributed by ukasp. |
Javascript
<script>// Javascript implementation of the above approach // Function to count pairs from an // array having GCD equal to // minimum element of that pair function countPairs(arr, N) { // Stores the resultant count let count = 0; // Iterate over the range [0, N - 2] for (let i = 0; i < N - 1; i++) { // Iterate over the range [i + 1, N] for (let j = i + 1; j < N; j++) { // If arr[i] % arr[j] is 0 // or arr[j] % arr[i] is 0 if (arr[i] % arr[j] == 0 || arr[j] % arr[i] == 0) { // Increment count by 1 count++; } } } // Return the resultant count return count; } // Driver Code let arr = [ 2, 3, 1, 2 ]; let N = arr.length; document.write(countPairs(arr, N)); </script> |
Output:
4
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the following observations:
- The minimum element of the pair should divide the maximum element of the pair, and it can be observed that element 1 can form a total of (N – 1) pairs.
- Every element can form
pair with itself where Y is the count of an array element. - The idea is to traverse over the divisors of every array element and increment the count of pairs that can be formed by the frequencies of the divisors.
pair with itself where Y is the Follow the steps below to solve the problem:
- Initialize a variable, say res, that stores the resultant count.
- Initialize a map, say mp, that stores the count of every array element.
- Traverse the array arr[] and increment the count of arr[i] in mp.
- Iterate over the pairs of map mp and perform the following operations:
- Store the value of array element in a variable say X and frequency of that number in a variable Y.
- If the value of X is 1, then increment the value of res by (N – 1) and continue.
- Increment the value of res by (Y*(Y – 1))/2.
- Now, iterate over the divisors of the integer X using a variable j and increment the res by mp[j].
- After completing the above steps, print the value of res as the total count obtained.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count pairs from an// array having GCD equal to// minimum element of that pairint CountPairs(int arr[], int N){ // Stores the resultant count int res = 0; // Stores the frequency of // each array element map<int, int> mp; // Traverse the array arr[] for (int i = 0; i < N; i++) { mp[arr[i]]++; } // Iterate over the Map mp for (auto p : mp) { // Stores the array element int x = p.first; // Stores the count // of array element x int y = p.second; // If x is 1 if (x == 1) { // Increment res by N-1 res += N - 1; continue; } // Increment res by yC2 res += (y * (y - 1)) / 2; // Iterate over the // range [2, sqrt(x)] for (int j = 2; j <= sqrt(x); j++) { // If x is divisible by j if (x % j == 0) { // Increment the value // of res by mp[j] res += mp[j]; // If j is not equal to x/j if (j != x / j) // Increment res // by mp[x/j] res += mp[x / j]; } } } // Return the resultant count return res;}// Driver Codeint main(){ int arr[] = { 2, 3, 1, 2 }; int N = sizeof(arr) / sizeof(arr[0]); cout << CountPairs(arr, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG { // Function to count pairs from an // array having GCD equal to // minimum element of that pair static int CountPairs(int arr[], int N) { // Stores the resultant count int res = 0; // Stores the frequency of // each array element Map<Integer, Integer> mp = new HashMap<>(); // Traverse the array arr[] for (int i = 0; i < N; i++) { Integer c = mp.get(arr[i]); mp.put(arr[i], (c == null) ? 1 : c + 1); } // Iterate over the Map mp Iterator<Map.Entry<Integer, Integer>> itr = mp.entrySet().iterator(); while(itr.hasNext()) { Map.Entry<Integer, Integer> entry = itr.next(); // Stores the array element int x = (int)entry.getKey(); // Stores the count // of array element x int y = (int)entry.getValue(); // If x is 1 if (x == 1) { // Increment res by N-1 res += N - 1; continue; } // Increment res by yC2 res += (y * (y - 1)) / 2; // Iterate over the // range [2, sqrt(x)] for (int j = 2; j <= Math.sqrt(x); j++) { // If x is divisible by j if (x % j == 0) { // Increment the value // of res by mp[j] res += mp.get(j); // If j is not equal to x/j if (j != x / j) // Increment res // by mp[x/j] res += mp.get((int)x / j); } } } // Return the resultant count return res; } // Driver Code public static void main (String[] args) { int arr[] = { 2, 3, 1, 2 }; int N = arr.length; System.out.println(CountPairs(arr, N)); }}// This code is contributed by Dharanendra L V. |
Python3
# Python3 program for the above approachfrom math import sqrt# Function to count pairs from an# array having GCD equal to# minimum element of that pairdef CountPairs(arr, N): # Stores the resultant count res = 0 # Stores the frequency of # each array element mp = {} # Traverse the array arr[] for i in range(N): if (arr[i] in mp): mp[arr[i]] += 1 else: mp[arr[i]] = 1 # Iterate over the Map mp for key, value in mp.items(): # Stores the array element x = key # Stores the count # of array element x y = value # If x is 1 if (x == 1): # Increment res by N-1 res += N - 1 continue # Increment res by yC2 res += (y * (y - 1)) // 2 # Iterate over the # range [2, sqrt(x)] for j in range(2, int(sqrt(x)) + 1, 1): # If x is divisible by j if (x % j == 0): # Increment the value # of res by mp[j] res += mp[j] # If j is not equal to x/j if (j != x // j): # Increment res # by mp[x/j] res += mp[x // j] # Return the resultant count return res# Driver Codeif __name__ == '__main__': arr = [ 2, 3, 1, 2 ] N = len(arr) print(CountPairs(arr, N))# This code is contributed by SURENDRA_GANGWAR |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to count pairs from an// array having GCD equal to// minimum element of that pairstatic int CountPairs(int []arr, int N){ // Stores the resultant count int res = 0; // Stores the frequency of // each array element Dictionary<int, int> mp = new Dictionary<int, int>(); // Traverse the array arr[] for(int i = 0; i < N; i++) { if (mp.ContainsKey(arr[i])) mp[arr[i]]++; else mp.Add(arr[i], 1); } // Iterate over the Map mp foreach(KeyValuePair<int, int> kvp in mp) { // Stores the array element int x = kvp.Key; // Stores the count // of array element x int y = kvp.Value; // If x is 1 if (x == 1) { // Increment res by N-1 res += N - 1; continue; } // Increment res by yC2 res += (y * (y - 1)) / 2; // Iterate over the // range [2, sqrt(x)] for(int j = 2; j <= Math.Sqrt(x); j++) { // If x is divisible by j if (x % j == 0) { // Increment the value // of res by mp[j] res += mp[j]; // If j is not equal to x/j if (j != x / j) // Increment res // by mp[x/j] res += mp[x / j]; } } } // Return the resultant count return res;}// Driver Codepublic static void Main(){ int []arr = { 2, 3, 1, 2 }; int N = arr.Length; Console.Write(CountPairs(arr, N));}}// This code is contributed by bgangwar59 |
Javascript
<script>// Javascript program for the above approach// Function to count pairs from an// array having GCD equal to// minimum element of that pairfunction CountPairs(arr, N){ // Stores the resultant count var res = 0; // Stores the frequency of // each array element var mp = new Map(); // Traverse the array arr[] 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); } } // Iterate over the Map mp mp.forEach((value, key) => { // Stores the array element var x = key; // Stores the count // of array element x var y = value; // If x is 1 if (x == 1) { // Increment res by N-1 res += N - 1; } // Increment res by yC2 res += parseInt((y * (y - 1)) / 2); // Iterate over the // range [2, sqrt(x)] for (var j = 2; j <= parseInt(Math.sqrt(x)); j++) { // If x is divisible by j if (x % j == 0) { // Increment the value // of res by mp[j] res += mp.get(j); // If j is not equal to x/j if (j != parseInt(x / j)) // Increment res // by mp[x/j] res += mp.get(parseInt(x / j)); } } }); // Return the resultant count return res;}// Driver Codevar arr = [2, 3, 1, 2 ];var N = arr.length;document.write( CountPairs(arr, N));</script> |
Output:
4
Time Complexity: O(N*?M), where M is the maximum element of the array.
Auxiliary Space: O(1)
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!
