Given an array a[] of non-negative integers. The task is to count the number of pairs (i, j) in the array such that LCM(a[i], a[j]) = HCF(a[i], a[j]).
Note: The pair (i, j) and (j, i) are considered same and i should not be equal to j.
Examples:
Input : a[] = {3, 4, 3, 4, 5}
Output : 2
Pairs are (3, 3) and (4, 4)
Input : a[] = {1, 1, 1}
Output : 3
Naive approach: Generate all possible pairs and count pairs with equal HCF and LCM.
C++
// Naive C++ program to count number of pairs// such that their hcf and lcm are equal#include <bits/stdc++.h>using namespace std;// Function to return HCF of two numbersint gcd(int a, int b){ if (a == 0) return b; return gcd(b % a, a);}// Function to return LCM of two numbersint lcm(int a, int b){ return (a * b) / gcd(a, b);}// Returns the number of valid pairsint countPairs(int arr[], int n){ int ans = 0; // initializing answer // Traversing the array. For each array // element, checking if it // follow the condition for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) if (lcm(arr[i], arr[j]) == gcd(arr[i], arr[j])) ans++; return ans;}// Driver functionint main(){ int arr[] = { 1, 1, 1 }; int n = sizeof(arr) / sizeof(arr[0]); cout << countPairs(arr, n); return 0;} |
Java
// Naive Java program to count number of pairs// such that their hcf and lcm are equalimport java.util.*;class GFG{ // Function to return HCF of two numbersstatic int gcd(int a, int b){ if (a == 0) return b; return gcd(b % a, a);} // Function to return LCM of two numbersstatic int lcm(int a, int b){ return (a * b) / gcd(a, b);} // Returns the number of valid pairsstatic int countPairs(int arr[], int n){ int ans = 0; // initializing answer // Traversing the array. For each array // element, checking if it // follow the condition for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) if (lcm(arr[i], arr[j]) == gcd(arr[i], arr[j])) ans++; return ans;} // Driver functionpublic static void main(String[] args){ int arr[] = { 1, 1, 1 }; int n = arr.length; System.out.print(countPairs(arr, n));}}// This code is contributed by Rajput-Ji |
Python3
# Naive Python program to count number of pairs# such that their hcf and lcm are equal# Function to return HCF of two numbersdef gcd(a, b): if (a == 0): return b; return gcd(b % a, a);# Function to return LCM of two numbersdef lcm(a, b): return (a * b) / gcd(a, b);# Returns the number of valid pairsdef countPairs(arr, n): ans = 0; # initializing answer # Traversing the array. For each array # element, checking if it # follow the condition for i in range(n): for j in range(i+1,n): if (lcm(arr[i], arr[j]) == gcd(arr[i], arr[j])): ans+=1; return ans;# Driver functionif __name__ == '__main__': arr = [ 1, 1, 1 ]; n = len(arr); print(countPairs(arr, n));# This code is contributed by 29AjayKumar |
C#
// Naive C# program to count number of pairs// such that their hcf and lcm are equalusing System;class GFG{ // Function to return HCF of two numbersstatic int gcd(int a, int b){ if (a == 0) return b; return gcd(b % a, a);} // Function to return LCM of two numbersstatic int lcm(int a, int b){ return (a * b) / gcd(a, b);} // Returns the number of valid pairsstatic int countPairs(int []arr, int n){ int ans = 0; // initializing answer // Traversing the array. For each array // element, checking if it // follow the condition for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) if (lcm(arr[i], arr[j]) == gcd(arr[i], arr[j])) ans++; return ans;} // Driver functionpublic static void Main(String[] args){ int []arr = { 1, 1, 1 }; int n = arr.Length; Console.Write(countPairs(arr, n));}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Naive Javascript program to count number of pairs// such that their hcf and lcm are equal// Function to return HCF of two numbersfunction gcd(a, b){ if (a == 0) return b; return gcd(b % a, a);}// Function to return LCM of two numbersfunction lcm(a, b){ return (a * b) / gcd(a, b);}// Returns the number of valid pairsfunction countPairs(arr, n){ var ans = 0; // initializing answer // Traversing the array. For each array // element, checking if it // follow the condition for (var i = 0; i < n; i++) for (var j = i + 1; j < n; j++) if (lcm(arr[i], arr[j]) == gcd(arr[i], arr[j])) ans++; return ans;}// Driver functionvar arr = [ 1, 1, 1 ];var n = arr.length;document.write(countPairs(arr, n));// This code is contributed by rutvik_56.</script> |
Output:
3
Time Complexity: O(n2 * log(max(a, b)))
Auxiliary Space: O(log(max(a, b)))
Efficient Approach: If we observe carefully, it can be proved that the HCF and LCM of two numbers can be equal only when the numbers are also equal.
Proof:
Let, HCF(a[i], a[j]) = LCM(a[i], a[j]) = K Since HCF(a[i], a[j]) = k, a[i] = k*n1, a[j] = k*n2, for some natural numbers n1, n2 We know that, HCF × LCM = Product of the two numbers Therefore, k*k = k*n1 × k*n2 or, n1*n2 = 1 Implies, n1 = n2 = 1, since n1, n2 are natural numbers. Therefore, a[i] = k*n1 = k, a[j] = k*n2 = k i.e. the numbers must be equal.
So we have to count pairs with same elements in the pair.
It is observed that only the pairs of the form (arr[i], arr[j]) where arr[i] = arr[j] will satisfy the given condition. So, the problem now gets reduced to finding the number of pairs (arr[i], arr[j]) such that arr[i] = arr[j].
Below is the implementation of the above approach:
C++
// C++ program to count number of pairs// such that their hcf and lcm are equal#include <bits/stdc++.h>using namespace std;// Function to count number of pairs// such that their hcf and lcm are equalint countPairs(int a[], int n){ // Store frequencies of array elements unordered_map<int, int> frequency; for (int i = 0; i < n; i++) { frequency[a[i]]++; } int count = 0; // Count of pairs (arr[i], arr[j]) // where arr[i] = arr[j] for (auto x : frequency) { int f = x.second; count += f * (f - 1) / 2; } // Count of pairs (arr[i], arr[j]) where // arr[i] = arr[j], return count;}// Driver functionint main(){ int arr[] = { 1, 1, 1 }; int n = sizeof(arr) / sizeof(arr[0]); cout << countPairs(arr, n); return 0;} |
Java
// Java program to count number of pairs// such that their hcf and lcm are equalimport java.util.*;class GFG{ // Function to count number of pairs// such that their hcf and lcm are equalstatic int countPairs(int arr[], int n){ // Store frequencies of array elements HashMap<Integer,Integer> frequency = new HashMap<Integer,Integer>(); for (int i = 0; i < n; i++) { if(frequency.containsKey(arr[i])){ frequency.put(arr[i], frequency.get(arr[i])+1); }else{ frequency.put(arr[i], 1); } } int count = 0; // Count of pairs (arr[i], arr[j]) // where arr[i] = arr[j] for (Map.Entry<Integer,Integer> x : frequency.entrySet()) { int f = x.getValue(); count += f * (f - 1) / 2; } // Count of pairs (arr[i], arr[j]) where // arr[i] = arr[j], return count;} // Driver functionpublic static void main(String[] args){ int arr[] = { 1, 1, 1 }; int n = arr.length; System.out.print(countPairs(arr, n));}}// This code contributed by sapnasingh4991 |
C#
// C# program to count number of pairs// such that their hcf and lcm are equalusing System;using System.Collections.Generic;class GFG{// Function to count number of pairs// such that their hcf and lcm are equalstatic int countPairs(int []a, int n){ // Store frequencies of array elements Dictionary<int, int> frequency = new Dictionary<int,int>(); for (int i = 0; i < n; i++) { if (frequency.ContainsKey(a[i])) { var val = frequency[a[i]]; frequency.Remove(a[i]); frequency.Add(a[i], val + 1); } else { frequency.Add(a[i], 1); } } int count = 0; // Count of pairs (arr[i], arr[j]) // where arr[i] = arr[j] foreach(KeyValuePair<int, int> entry in frequency) { int f = entry.Value; count += f * (f - 1) / 2; } // Count of pairs (arr[i], arr[j]) where // arr[i] = arr[j], return count;}// Driver functionpublic static void Main(String[] args){ int []arr = { 1, 1, 1 }; int n = arr.Length; Console.Write(countPairs(arr, n));}}// This code is contributed by shivanisinghss2110 |
Python3
# Python 3 program to count number of pairs# such that their hcf and lcm are equalfrom collections import defaultdict # Function to count number of pairs# such that their hcf and lcm are equaldef countPairs(a, n): # Store frequencies of array elements frequency = defaultdict(int) for i in range(n) : frequency[a[i]] += 1 count = 0 # Count of pairs (arr[i], arr[j]) # where arr[i] = arr[j] for x in frequency.keys(): f = frequency[x] count += f * (f - 1) // 2 # Count of pairs (arr[i], arr[j]) where # arr[i] = arr[j], return count # Driver functionif __name__ == "__main__": arr = [ 1, 1, 1 ] n = len(arr) print(countPairs(arr, n))# This code is contributed by chitranayal |
Javascript
<script>// JavaScript program to count number of pairs// such that their hcf and lcm are equal// Function to count number of pairs// such that their hcf and lcm are equalfunction countPairs(arr,n){ // Store frequencies of array elements let frequency = new Map(); for (let i = 0; i < n; i++) { if(frequency.has(arr[i])){ frequency.set(arr[i], frequency.get(arr[i])+1); }else{ frequency.set(arr[i], 1); } } let count = 0; // Count of pairs (arr[i], arr[j]) // where arr[i] = arr[j] for (let [key, value] of frequency.entries()) { let f = value; count += f * (f - 1) / 2; } // Count of pairs (arr[i], arr[j]) where // arr[i] = arr[j], return count;}// Driver functionlet arr=[1, 1, 1 ];let n = arr.length;document.write(countPairs(arr, n));// This code is contributed by avanitrachhadiya2155</script> |
Output:
3
Time Complexity: O(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!