Count number of pairs (i, j) from an array such that arr[i] * j = arr[j] * i
Given an array arr[] of size N, the task is to count the number of pairs (i, j) possible from the array such that arr[j] * i = arr[i] * j, where 1 ≤ i < j ≤ N.
Examples:
Input: arr[] = {1, 3, 5, 6, 5}
Output: 2
Explanation:
Pair (1, 5) satisfies the condition, since arr[1] * 5 = arr[5] * 1.
Pair (2, 4) satisfies the condition, since arr[2] * 4 = arr[4] * 2.
Therefore, total number of pairs satisfying the given condition is 2.Input: arr[] = {2, 1, 3}
Output: 0
Naive Approach: The simplest approach to solve the problem is to generate all possible pairs from the array and check for each pair, whether the given condition satisfies or not. Increase count for the pairs for which the condition is satisfied. Finally, print the count of all such pairs.
Below is the implementation of the above idea:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count pairs from an // array satisfying given conditions void countPairs( int arr[], int N) { // Stores the total // count of pairs int count = 0; for ( int i = 1; i <= N; i++) { for ( int j = i + 1; j <= N; j++) { // Note: Indices are 1 based according to // question if ((arr[j - 1] * i) == (arr[i - 1] * j)) { count++; } } } cout << count; } // Driver Code int main() { // Given array int arr[] = { 1, 3, 5, 6, 5 }; // Size of the array int N = sizeof (arr) / sizeof (arr[0]); // Function call to count pairs // satisfying given conditions countPairs(arr, N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to count pairs from an // array satisfying given conditions static void countPairs( int [] arr, int N) { // Stores the total // count of pairs int count = 0 ; for ( int i = 1 ; i <= N; i++) { for ( int j = i + 1 ; j <= N; j++) { // Note: Indices are 1 based according to // question if ((arr[j - 1 ] * i) == (arr[i - 1 ] * j)) { count++; } } } System.out.print(count); } // Driver Code public static void main(String args[]) { // Given array int [] arr = { 1 , 3 , 5 , 6 , 5 }; // Size of the array int N = arr.length; // Function call to count pairs // satisfying given conditions countPairs(arr, N); } } |
Python3
# Python code for the above approach # Function to count pairs from an # array satisfying given conditions def countPairs(arr, N): # Stores the total # count of pairs count = 0 for i in range ( 1 , N + 1 ): for j in range (i + 1 , N + 1 ): # Note: Indices are 1 based according to # question if (arr[j - 1 ] * i) = = (arr[i - 1 ] * j): count + = 1 print (count) # Given array arr = [ 1 , 3 , 5 , 6 , 5 ] # Size of the array N = len (arr) # Function call to count pairs # satisfying given conditions countPairs(arr, N) |
C#
// C# code to implement the approach using System; using System.Collections.Generic; public class Gfg { // Function to count pairs from an // array satisfying given conditions static void countPairs( int []arr, int N) { // Stores the total // count of pairs int count = 0; for ( int i = 1; i <= N; i++) { for ( int j = i + 1; j <= N; j++) { // Note: Indices are 1 based according to // question if ((arr[j - 1] * i) == (arr[i - 1] * j)) { count++; } } } Console.WriteLine(count); } // Driver Code public static void Main( string [] args) { // Given array int [] arr = { 1, 3, 5, 6, 5 }; // Size of the array int N = arr.Length; // Function call to count pairs // satisfying given conditions countPairs(arr, N); } } |
Javascript
// Javascript program for the above approach // Function to count pairs from an // array satisfying given conditions function countPairs(arr, N) { // Stores the total // count of pairs let count = 0; for (let i = 1; i <= N; i++) { for (let j = i + 1; j <= N; j++) { // Note: Indices are 1 based according to // question if ((arr[j - 1] * i) == (arr[i - 1] * j)) { count++; } } } document.write(count); } // Driver Code // Given array let arr = [1, 3, 5, 6, 5 ]; // Size of the array let N = arr.length; // Function call to count pairs // satisfying given conditions countPairs(arr, N); |
2
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is based on the rearrangement of the given equation arr[i] * j = arr[j] * i to arr[i] / i = arr[j] / j.
Follow the steps below to solve the problem:
- Initialize a variable, say count, to store the total count of pairs satisfying the given conditions.
- Initialize an Unordered Map, say mp, to count the frequency of values arr[i] / i.
- Traverse the array arr[] and update the frequencies of arr[i]/i in the Map.
- Print the count as the answer.
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 satisfying given conditions void countPairs( int arr[], int N) { // Stores the total // count of pairs int count = 0; // Stores count of a[i] / i unordered_map< double , int > mp; // Traverse the array for ( int i = 0; i < N; i++) { double val = 1.0 * arr[i]; double idx = 1.0 * (i + 1); // Updating count count += mp[val / idx]; // Update frequency // in the Map mp[val / idx]++; } // Print count of pairs cout << count; } // Driver Code int main() { // Given array int arr[] = { 1, 3, 5, 6, 5 }; // Size of the array int N = sizeof (arr) / sizeof (arr[0]); // Function call to count pairs // satisfying given conditions countPairs(arr, N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to count pairs from an // array satisfying given conditions static void countPairs( int []arr, int N) { // Stores the total // count of pairs int count = 0 ; // Stores count of a[i]/i Map<Double, Integer> mp = new HashMap<Double, Integer>(); // Traverse the array for ( int i = 0 ; i < N; i++) { Double val = 1.0 * arr[i]; Double idx = 1.0 * (i + 1 ); // Updating count if (mp.containsKey(val / idx)) count += mp.get(val/idx); // Update frequency // in the Map if (mp.containsKey(val / idx)) mp.put(val / idx, mp.getOrDefault(val / idx, 0 ) + 1 ); else mp.put(val/idx, 1 ); } // Print count of pairs System.out.print(count); } // Driver Code public static void main(String args[]) { // Given array int []arr = { 1 , 3 , 5 , 6 , 5 }; // Size of the array int N = arr.length; // Function call to count pairs // satisfying given conditions countPairs(arr, N); } } // This code is contributed by ipg2016107. |
Python3
# Python3 program for the above approach from collections import defaultdict # Function to count pairs from an # array satisfying given conditions def countPairs(arr, N): # Stores the total # count of pairs count = 0 # Stores count of a[i] / i mp = defaultdict( int ) # Traverse the array for i in range (N): val = 1.0 * arr[i] idx = 1.0 * (i + 1 ) # Updating count count + = mp[val / idx] # Update frequency # in the Map mp[val / idx] + = 1 # Print count of pairs print (count) # Driver Code if __name__ = = "__main__" : # Given array arr = [ 1 , 3 , 5 , 6 , 5 ] # Size of the array N = len (arr) # Function call to count pairs # satisfying given conditions countPairs(arr, N) # This code is contributed by ukasp |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to count pairs from an // array satisfying given conditions static void countPairs( int []arr, int N) { // Stores the total // count of pairs int count = 0; // Stores count of a[i]/i Dictionary< double , int > mp = new Dictionary< double , int >(); // Traverse the array for ( int i = 0; i < N; i++) { double val = 1.0 * arr[i]; double idx = 1.0 * (i + 1); // Updating count if (mp.ContainsKey(val / idx)) count += mp[val/idx]; // Update frequency // in the Map if (mp.ContainsKey(val / idx)) mp[val / idx]++; else mp[val/idx] = 1; } // Print count of pairs Console.WriteLine(count); } // Driver Code public static void Main() { // Given array int []arr = { 1, 3, 5, 6, 5 }; // Size of the array int N = arr.Length; // Function call to count pairs // satisfying given conditions countPairs(arr, N); } } // This code is contributed by SURENDRA_GANGWAR |
Javascript
<script> // Javascript program for the above approach // Function to count pairs from an // array satisfying given conditions function countPairs(arr, N) { // Stores the total // count of pairs var count = 0; // Stores count of a[i] / i var mp = new Map(); // Traverse the array for ( var i = 0; i < N; i++) { var val = 1.0 * arr[i]; var idx = 1.0 * (i + 1); // Updating count count += mp.has(val/idx)?mp.get(val/idx):0 // Update frequency // in the Map if (mp.has(val/idx)) mp.set(val/idx, mp.get(val/idx)+1) else mp.set(val/idx, 1) } // Print count of pairs document.write( count); } // Driver Code // Given array var arr = [1, 3, 5, 6, 5]; // Size of the array var N = arr.length; // Function call to count pairs // satisfying given conditions countPairs(arr, N); // This code is contributed by itsok. </script> |
2
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us