Given an array arr[] consisting of N pairs of the form {A, B}, the task is to count the pairs of indices (i, j) such that the ratio of pairs of arr[i] and arr[j] are the same.
Examples:
Input: arr[] = {{2, 6}, {1, 3}, {8, 24}}
Output: 3
Explanation:
Following are the pairs of indices whose ratios are the same:
- (0, 1): Ratio of pair arr[0] = 2/6 = 1/3 and the ratio of pair arr[1] = 1/3, which are the same.
- (0, 2): Ratio of pair arr[0] = 2/6 = 1/3 and the ratio of pair arr[2] = 8/24 = 1/3, which are the same.
- (1, 2): Ratio of pair arr[1] = 1/3 and the ratio of pair arr[2] = 8/24 = 1/3, which are the same.
Therefore, the count of such pairs are 3.
Input: arr[] = {{4, 5}, {7, 8}}
Output: 0
Naive Approach: The simplest approach to solve the given problem is to generate all possible pairs of the given array and count those pairs whose ratios are the same. After checking for all the pairs, print the total count of pairs 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 find the count of pairs// having same ratiolong long pairsWithSameRatio( vector<pair<int, int> >& arr){ // Stores the total count of pairs int count = 0; // Traverse the array arr[] for (int i = 0; i < arr.size(); i++) { // Find the first ratio double ratio1 = (double)arr[i].first / (double)arr[i].second; for (int j = i + 1; j < arr.size(); j++) { // Find the second ratio double ratio2 = (double)arr[j].first / (double)arr[j].second; // Increment the count if // the ratio are the same if (ratio1 == ratio2) { count++; } } } // Return the total count obtained return count;}// Driver Codeint main(){ vector<pair<int, int> > arr = { { 2, 6 }, { 1, 3 }, { 8, 24 }, { 4, 12 }, { 16, 48 } }; cout << pairsWithSameRatio(arr); return 0;} |
Java
// Java program for the above approachclass GFG { static class pair { int first, second; public pair(int first, int second) { this.first = first; this.second = second; } } // Function to find the count of pairs // having same ratio static long pairsWithSameRatio(pair[] arr) { // Stores the total count of pairs int count = 0; // Traverse the array arr[] for (int i = 0; i < arr.length; i++) { // Find the first ratio double ratio1 = (double) arr[i].first / (double) arr[i].second; for (int j = i + 1; j < arr.length; j++) { // Find the second ratio double ratio2 = (double) arr[j].first / (double) arr[j].second; // Increment the count if // the ratio are the same if (ratio1 == ratio2) { count++; } } } // Return the total count obtained return count; } // Driver Code public static void main(String[] args) { pair[] arr = { new pair(2, 6), new pair(1, 3), new pair(8, 24), new pair(4, 12), new pair(16, 48) }; System.out.print(pairsWithSameRatio(arr)); }}// This code is contributed by shikhasingrajput |
Python3
# Python 3 program for the above approach# Function to find the count of pairs# having same ratiodef pairsWithSameRatio(arr): # Stores the total count of pairs count = 0 # Traverse the array arr[] for i in range(len(arr)): # Find the first ratio ratio1 = arr[i][0]//arr[i][1] for j in range(i + 1, len(arr), 1): # Find the second ratio ratio2 = arr[j][0]//arr[j][1] # Increment the count if # the ratio are the same if (ratio1 == ratio2): count += 1 # Return the total count obtained return count# Driver Codeif __name__ == '__main__': arr = [[2, 6],[1, 3],[8, 24],[4, 12],[16, 48]] print(pairsWithSameRatio(arr)) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approachusing System;public class GFG { class pair { public int first, second; public pair(int first, int second) { this.first = first; this.second = second; } } // Function to find the count of pairs // having same ratio static long pairsWithSameRatio(pair[] arr) { // Stores the total count of pairs int count = 0; // Traverse the array []arr for (int i = 0; i < arr.Length; i++) { // Find the first ratio double ratio1 = (double) arr[i].first / (double) arr[i].second; for (int j = i + 1; j < arr.Length; j++) { // Find the second ratio double ratio2 = (double) arr[j].first / (double) arr[j].second; // Increment the count if // the ratio are the same if (ratio1 == ratio2) { count++; } } } // Return the total count obtained return count; } // Driver Code public static void Main(String[] args) { pair[] arr = { new pair(2, 6), new pair(1, 3), new pair(8, 24), new pair(4, 12), new pair(16, 48) }; Console.Write(pairsWithSameRatio(arr)); }} // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find the count of pairs // having same ratio function pairsWithSameRatio( arr) { // Stores the total count of pairs let count = 0; // Traverse the array arr[] for (let i = 0; i < arr.length; i++) { // Find the first ratio let ratio1 = arr[i].first / arr[i].second; for (let j = i + 1; j < arr.length; j++) { // Find the second ratio ratio2 = arr[j].first / arr[j].second; // Increment the count if // the ratio are the same if (ratio1 == ratio2) { count++; } } } // Return the total count obtained return count; } // Driver Code let arr = [ { first: 2, second: 6 }, { first: 1, second: 3 }, { first: 8, second: 24 }, { first: 4, second: 12 }, { first: 16, second: 48 } ] document.write(pairsWithSameRatio(arr)); // This code is contributed by Potta Lokesh </script> |
Output:
10
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized by using the map by storing the frequency of the ratios of every pair in the given array arr[] and then count the total number of pairs formed. Follow the step below to solve the given problem:
- Initialize a variable, say ans as 0 that stores the total count of pairs having the same ratio.
- Create an unordered map, say Map that stores the key as the ratio of pair of array elements and value as their frequency.
- Traverse the given array arr[] and for each pair {A, B} increment the frequency of A/B in the map by 1.
- Iterate over the map Map and for each key-value pair if the frequency of any key is greater than 1 then add the value of frequency*(frequency – 1)/2 to the variable ans storing the resultant count of pairs with the current key as the ratio.
- After completing the above steps, print the value of ans 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;// Returns factorial of Nint fact(int n){ int res = 1; for (int i = 2; i <= n; i++) res = res * i; return res;}// Return the value of nCrint nCr(int n, int r){ return fact(n) / (fact(r) * fact(n - r));}// Function to count the number of pairs// having the same ratioint pairsWithSameRatio( vector<pair<int, int> >& arr){ // Stores the frequency of the ratios unordered_map<double, int> mp; int ans = 0; // Filling the map for (auto x : arr) { mp[x.first / x.second] += 1; } for (auto x : mp) { int val = x.second; // Find the count of pairs with // current key as the ratio if (val > 1) { ans += nCr(val, 2); } } // Return the total count return ans;}// Driver Codeint main(){ vector<pair<int, int> > arr = { { 2, 6 }, { 1, 3 }, { 8, 24 }, { 4, 12 }, { 16, 48 } }; cout << pairsWithSameRatio(arr); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{static class pair{ int first, second; public pair(int first, int second) { this.first = first; this.second = second; } } // Returns factorial of Nstatic int fact(int n){ int res = 1; for (int i = 2; i <= n; i++) res = res * i; return res;}// Return the value of nCrstatic int nCr(int n, int r){ return fact(n) / (fact(r) * fact(n - r));}// Function to count the number of pairs// having the same ratiostatic int pairsWithSameRatio( pair []arr){ // Stores the frequency of the ratios Map<Double, Integer> mp = new HashMap<Double, Integer>(); int ans = 0; // Filling the map for (pair x : arr) { if(mp.containsKey((double) (x.first / x.second))){ mp.put((double) (x.first / x.second), mp.get((double) (x.first / x.second))+1); } else{ mp.put((double)(x.first / x.second), 1); } } for (Map.Entry<Double,Integer> x : mp.entrySet()){ int val = x.getValue(); // Find the count of pairs with // current key as the ratio if (val > 1) { ans += nCr(val, 2); } } // Return the total count return ans;}// Driver Codepublic static void main(String[] args){ pair []arr = { new pair( 2, 6 ), new pair( 1, 3 ), new pair( 8, 24 ), new pair( 4, 12 ), new pair( 16, 48 ) }; System.out.print(pairsWithSameRatio(arr));}}// This code is contributed by 29AjayKumar |
Python3
# Python 3 program for the above approachfrom collections import defaultdict# Returns factorial of Ndef fact(n): res = 1 for i in range(2, n + 1): res = res * i return res# Return the value of nCrdef nCr(n, r): return fact(n) // (fact(r) * fact(n - r))# Function to count the number of pairs# having the same ratiodef pairsWithSameRatio(arr): # Stores the frequency of the ratios mp = defaultdict(int) ans = 0 # Filling the map for x in arr: mp[x[0] // x[1]] += 1 for x in mp: val = mp[x] # Find the count of pairs with # current key as the ratio if (val > 1): ans += nCr(val, 2) # Return the total count return ans# Driver Codeif __name__ == "__main__": arr = [[2, 6], [1, 3], [8, 24], [4, 12], [16, 48]] print(pairsWithSameRatio(arr)) # This code is contributed by ukasp. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{class pair{ public int first, second; public pair(int first, int second) { this.first = first; this.second = second; } } // Returns factorial of Nstatic int fact(int n){ int res = 1; for (int i = 2; i <= n; i++) res = res * i; return res;}// Return the value of nCrstatic int nCr(int n, int r){ return fact(n) / (fact(r) * fact(n - r));}// Function to count the number of pairs// having the same ratiostatic int pairsWithSameRatio( pair []arr){ // Stores the frequency of the ratios Dictionary<Double, int> mp = new Dictionary<Double, int>(); int ans = 0; // Filling the map foreach (pair x in arr) { if(mp.ContainsKey((double) (x.first / x.second))){ mp[(double) (x.first / x.second)]=mp[(double) (x.first / x.second)]+1; } else{ mp.Add((double)(x.first / x.second), 1); } } foreach (KeyValuePair<Double,int> x in mp){ int val = x.Value; // Find the count of pairs with // current key as the ratio if (val > 1) { ans += nCr(val, 2); } } // Return the total count return ans;}// Driver Codepublic static void Main(String[] args){ pair []arr = { new pair( 2, 6 ), new pair( 1, 3 ), new pair( 8, 24 ), new pair( 4, 12 ), new pair( 16, 48 ) }; Console.Write(pairsWithSameRatio(arr));}}// This code is contributed by 29AjayKumar |
Javascript
<script>// javascript program for the above approach class pair { constructor(first , second) { this.first = first; this.second = second; } } // Returns factorial of N function fact(n) { var res = 1; for (i = 2; i <= n; i++) res = res * i; return res; } // Return the value of nCr function nCr(n , r) { return fact(n) / (fact(r) * fact(n - r)); } // Function to count the number of pairs // having the same ratio function pairsWithSameRatio( arr) { // Stores the frequency of the ratios var mp = new Map(); var ans = 0; // Filling the map for (var x of arr) { if (mp.has( (x.first / x.second))) { mp.set((x.first / x.second), mp.get( (x.first / x.second)) + 1); } else { mp.set( (x.first / x.second), 1); } } for ( x of mp) { var val = x[1]; // Find the count of pairs with // current key as the ratio if (val > 1) { ans += nCr(val, 2); } } // Return the total count return ans; } // Driver Code var arr = [ new pair(2, 6), new pair(1, 3), new pair(8, 24), new pair(4, 12), new pair(16, 48) ]; document.write(pairsWithSameRatio(arr));// This code is contributed by Rajput-Ji </script> |
Output:
10
Time Complexity: O(N)
Auxiliary Space: O(N)
Take a part in the ongoing discussion
