Given an array arr[] consisting of N integers, the task is to count the number of valid pairs (i, j) such that arr[i] + arr[j] = arr[i] / arr[j].
Examples:
Input: arr[] = {-4, -3, 0, 2, 1}
Output: 1
Explanation: The only possible pair is (0, 3) which satisfies the condition ( -4 + 2 = -4 / 2 (= -2) ).Input: arr[] = {1, 2, 3, 4, 5}
Output: 0
Naive Approach: The simple approach is to generate all possible pairs of the given array and count the number of pairs whose sum is equal to their division. After checking, all the pairs print the final count of possible pairs.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count all pairs (i, j) // such that a[i] + [j] = a[i] / a[j] int countPairs( int a[], int n) { // Stores total count of pairs int count = 0; // Generate all possible pairs for ( int i = 0; i < n; i++) { for ( int j = i + 1; j < n; j++) { if (a[j] != 0 && a[i] % a[j] == 0) { // If a valid pair is found if ((a[i] + a[j]) == (a[i] / a[j])) // Increment count count++; } } } // Return the final count return count; } // Driver Code int main() { int arr[] = { -4, -3, 0, 2, 1 }; int N = sizeof (arr) / sizeof (arr[0]); cout << countPairs(arr, N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to count all pairs (i, j) // such that a[i] + [j] = a[i] / a[j] static int countPairs( int a[], int n) { // Stores total count of pairs int count = 0 ; // Generate all possible pairs for ( int i = 0 ; i < n; i++) { for ( int j = i + 1 ; j < n; j++) { if (a[j] != 0 && a[i] % a[j] == 0 ) { // If a valid pair is found if ((a[i] + a[j]) == (a[i] / a[j])) // Increment count count++; } } } // Return the final count return count; } // Driver Code public static void main(String[] args) { int arr[] = { - 4 , - 3 , 0 , 2 , 1 }; int N = arr.length; System.out.print(countPairs(arr, N)); } } // This code is contributed by code_hunt. |
Python3
# Python3 program for the above approach # Function to count all pairs (i, j) # such that a[i] + [j] = a[i] / a[j] def countPairs(a, n): # Stores total count of pairs count = 0 # Generate all possible pairs for i in range (n): for j in range (i + 1 , n): if (a[j] ! = 0 and a[i] % a[j] = = 0 ): # If a valid pair is found if ((a[i] + a[j]) = = (a[i] / / a[j])): # Increment count count + = 1 # Return the final count return count # Driver Code if __name__ = = '__main__' : arr = [ - 4 , - 3 , 0 , 2 , 1 ] N = len (arr) print (countPairs(arr, N)) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approach using System; class GFG { // Function to count all pairs (i, j) // such that a[i] + [j] = a[i] / a[j] static int countPairs( int [] a, int n) { // Stores total count of pairs int count = 0; // Generate all possible pairs for ( int i = 0; i < n; i++) { for ( int j = i + 1; j < n; j++) { if (a[j] != 0 && a[i] % a[j] == 0) { // If a valid pair is found if ((a[i] + a[j]) == (a[i] / a[j])) // Increment count count++; } } } // Return the final count return count; } // Driver code static void Main() { int [] arr = { -4, -3, 0, 2, 1 }; int N = arr.Length; Console.WriteLine(countPairs(arr, N)); } } // This code is contributed by divyeshrabadiya07. |
Javascript
<script> // JavaScript program for the above approach // Function to count all pairs (i, j) // such that a[i] + [j] = a[i] / a[j] function countPairs(a, n) { // Stores total count of pairs var count = 0; // Generate all possible pairs for ( var i = 0; i < n; i++) { for ( var j = i + 1; j < n; j++) { if (a[j] != 0 && a[i] % a[j] == 0) { // If a valid pair is found if ((a[i] + a[j]) == (a[i] / a[j])) // Increment count count++; } } } // Return the final count return count; } // Driver Code var arr = [-4, -3, 0, 2, 1 ]; var N = arr.length; document.write( countPairs(arr, N)); </script> |
1
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized by simplifying the given expression and using a Map to count the number of pairs that satisfy the below-simplified condition:
Suppose X and Y are numbers present in indices i and j, then the condition that needs to be satisfied is:
=> X + Y = X/Y
=> X = Y 2/(1 – Y)
Follow the steps below to solve the above problem:
- Initialize a variable, say, count, to store the count of all possible pairs satisfying the required condition.
- Initialize a Map to store the frequencies of values of the above expression obtained for each array element.
- Traverse the given array using the variable i and perform the following steps:
- If arr[i] is not equal to 1 and 0, then calculate arr[i] 2/(1 – arr[i]), say X.
- Add the frequency of X in the Map to count.
- Increase the frequency of arr[i] by 1 in the Map.
- After completing the above steps, print the value of the count 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 find number of pairs // with equal sum and quotient // from a given array int countPairs( int a[], int n) { // Store the count of pairs int count = 0; // Stores frequencies map< double , int > mp; // Traverse the array for ( int i = 0; i < n; i++) { int y = a[i]; // If y is neither 1 or 0 if (y != 0 && y != 1) { // Evaluate x double x = ((y * 1.0) / (1 - y)) * y; // Increment count by frequency // of x count += mp[x]; } // Update map mp[y]++; } // Print the final count return count; } // Driver Code int main() { int arr[] = { -4, -3, 0, 2, 1 }; int N = sizeof (arr) / sizeof (arr[0]); // Function Call cout << countPairs(arr, N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to find number of pairs // with equal sum and quotient // from a given array static int countPairs( int a[], int n) { // Store the count of pairs int count = 0 ; // Stores frequencies HashMap<Double, Integer> mp = new HashMap<Double, Integer>(); // Traverse the array for ( int i = 0 ; i < n; i++) { double y = a[i]; // If y is neither 1 or 0 if (y != 0 && y != 1 ) { // Evaluate x double x = ((y * 1.0 ) / ( 1 - y)) * y; // Increment count by frequency // of x if (mp.containsKey(x)) count += mp.get(x); } // Update map if (mp.containsKey(y)){ mp.put(y, mp.get(y)+ 1 ); } else { mp.put(y, 1 ); } } // Print the final count return count; } // Driver Code public static void main(String[] args) { int arr[] = { - 4 , - 3 , 0 , 2 , 1 }; int N = arr.length; // Function Call System.out.print(countPairs(arr, N)); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approach # Function to find number of pairs # with equal sum and quotient # from a given array def countPairs(a, n) : # Store the count of pairs count = 0 # Stores frequencies mp = {} # Traverse the array for i in range (n): y = a[i] # If y is neither 1 or 0 if (y ! = 0 and y ! = 1 ) : # Evaluate x x = (((y * 1.0 ) / / ( 1 - y)) * y) # Increment count by frequency # of x count + = mp.get(x, 0 ) # Update map mp[y] = mp.get(y, 0 ) + 1 # Print final count return count # Driver Code arr = [ - 4 , - 3 , 0 , 2 , 1 ] N = len (arr) # Function Call print (countPairs(arr, N)) # This code is contributed by susmitakundugoaldanga. |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function to find number of pairs // with equal sum and quotient // from a given array static int countPairs( int [] a, int n) { // Store the count of pairs int count = 0; // Stores frequencies Dictionary< double , int > mp = new Dictionary< double , int >(); // Traverse the array for ( int i = 0; i < n; i++) { int y = a[i]; // If y is neither 1 or 0 if (y != 0 && y != 1) { // Evaluate x double x = ((y * 1.0) / (1 - y)) * y; // Increment count by frequency // of x if (!mp.ContainsKey(x)) mp[x] = 0; count += mp[x]; } // Update map if (!mp.ContainsKey(y)) mp[y] = 0; mp[y]++; } // Print the final count return count; } // Driver Code public static void Main() { int [] arr = { -4, -3, 0, 2, 1 }; int N = arr.Length; // Function Call Console.Write(countPairs(arr, N)); } } // This code is contributed by ukasp. |
Javascript
<script> // JavaScript program for the above approach // Function to find number of pairs // with equal sum and quotient // from a given array function countPairs(a, n) { // Store the count of pairs let count = 0; // Stores frequencies let mp = new Map(); // Traverse the array for (let i = 0; i < n; i++) { let y = a[i]; // If y is neither 1 or 0 if (y != 0 && y != 1) { // Evaluate x let x = ((y * 1.0) / (1 - y)) * y; // Increment count by frequency // of x if (mp.has(x)) count += mp.get(x); } // Update map if (mp.has(y)){ mp.set(y, mp.get(y)+1); } else { mp.set(y, 1); } } // Print the final count return count; } // Driver Code let arr = [ -4, -3, 0, 2, 1 ]; let N = arr.length; // Function Call document.write(countPairs(arr, N)); </script> |
1
Time Complexity: O(N*log N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!