Given an array arr[] of length N, count the number of pairs (i, j) such that arr[i] * arr[j] = arr[i] + arr[j] and 0 <= i < j <= N. It is also given that elements of the array can be any positive integers including zero.
Examples:
Input : arr[] = {2, 0, 3, 2, 0}
Output : 2
Input : arr[] = {1, 2, 3, 4}
Output : 0
Simple solution:
We can generate all possible pairs of the array and count those pairs which satisfy the given condition.
Below is the implementation of the above approach:
CPP
// C++ program to count pairs (i, j)// such that arr[i] * arr[j] = arr[i] + arr[j]#include <bits/stdc++.h>using namespace std;// Function to return the count of pairs(i, j)// such that arr[i] * arr[j] = arr[i] + arr[j]long countPairs(int arr[], int n){ long count = 0; for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { // Increment count if condition satisfy if (arr[i] * arr[j] == arr[i] + arr[j]) count++; } } // Return count of pairs return count;}// Driver codeint main(){ int arr[] = { 2, 0, 3, 2, 0 }; int n = sizeof(arr) / sizeof(arr[0]); // Get and print count of pairs cout << countPairs(arr, n); return 0;} |
Java
// Java program to count pairs (i, j)// such that arr[i] * arr[j] = arr[i] + arr[j]class GFG { // Function to return the count of pairs(i, j) // such that arr[i] * arr[j] = arr[i] + arr[j] static long countPairs(int arr[], int n) { long count = 0; for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { // Increment count if condition satisfy if (arr[i] * arr[j] == arr[i] + arr[j]) count++; } } // Return count of pairs return count; } // Driver code public static void main(String[] args) { int arr[] = { 2, 0, 3, 2, 0 }; int n = arr.length; // Get and print count of pairs System.out.println(countPairs(arr, n)); }} |
Python3
# Python3 program to count pairs (i, j) # such that arr[i] * arr[j] = arr[i] + arr[j] # Function to return the count of pairs(i, j) # such that arr[i] * arr[j] = arr[i] + arr[j] def countPairs(arr, n) : count = 0; for i in range(n - 1) : for j in range(i + 1, n) : # Increment count if condition satisfy if (arr[i] * arr[j] == arr[i] + arr[j]) : count += 1; # Return count of pairs return count; # Driver code if __name__ == "__main__" : arr = [ 2, 0, 3, 2, 0 ]; n = len(arr); # Get and print count of pairs print(countPairs(arr, n)); # This code is contributed by AnkitRai01 |
C#
// C# program to count pairs (i, j)// such that arr[i] * arr[j] = arr[i] + arr[j]using System;class GFG { // Function to return the count of pairs(i, j) // such that arr[i] * arr[j] = arr[i] + arr[j] static long countPairs(int[] arr, int n) { long count = 0; for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { // Increment count if condition satisfy if (arr[i] * arr[j] == arr[i] + arr[j]) count++; } } // Return count of pairs return count; } // Driver code public static void Main(string[] args) { int[] arr = { 2, 0, 3, 2, 0 }; int n = arr.Length; // Get and print count of pairs Console.WriteLine(countPairs(arr, n)); }} |
Javascript
<script>// Function to return the count of pairs(i, j)// such that arr[i] * arr[j] = arr[i] + arr[j]function countPairs(arr, n){let count = 0;for (let i = 0; i < n - 1; i++) {for (let j = i + 1; j < n; j++) {// Increment count if condition satisfyif (arr[i] * arr[j] == arr[i] + arr[j])count++;}}// Return count of pairsreturn count;}let arr = [ 2, 0, 3, 2, 0 ];let n = arr.length;document.write(countPairs(arr, n));// This code is contributed by khatriharsh281</script> |
Output:
2
Time Complexity: O(n2)
Auxiliary Space: O(12)
Efficient Solution:
Taking arr[i] as x and arr[j] as y, we can rewrite the given condition as the following equation.
xy = x + y xy - x - y = 0 xy - x - y + 1 = 1 x(y - 1) -(y - 1) = 1 (x - 1)(y - 1) = 1 Case 1: x - 1 = 1 i.e x = 2 y - 1 = 1 i.e y = 2 Case 2: x - 1 = -1 i.e x = 0 y - 1 = -1 i.e y = 0
So, now we know that the condition arr[i] * arr[j] = arr[i] + arr[j] will satisfy only if either arr[i] = arr[j] = 0 or arr[i] = arr[j] = 2.
All we need to do is to count the occurrence of 2’s and 0’s. We can then get the number of pairs using formula
(count * (count - 1)) / 2
Below is the implementation of the above approach:
CPP
// C++ program to count pairs (i, j)// such that arr[i] * arr[j] = arr[i] + arr[j]#include <bits/stdc++.h>using namespace std;// Function to return the count of pairs(i, j)// such that arr[i] * arr[j] = arr[i] + arr[j]long countPairs(int arr[], int n){ int countZero = 0; int countTwo = 0; // Count number of 0's and 2's in the array for (int i = 0; i < n; i++) { if (arr[i] == 0) countZero++; else if (arr[i] == 2) countTwo++; } // Total pairs due to occurrence of 0's long pair0 = (countZero * (countZero - 1)) / 2; // Total pairs due to occurrence of 2's long pair2 = (countTwo * (countTwo - 1)) / 2; // Return count of all pairs return pair0 + pair2;}// Driver codeint main(){ int arr[] = { 2, 0, 3, 2, 0 }; int n = sizeof(arr) / sizeof(arr[0]); // Get and print count of pairs cout << countPairs(arr, n); return 0;} |
Java
// Java program to count pairs (i, j)// such that arr[i] * arr[j] = arr[i] + arr[j]class GFG { // Function to return the count of pairs(i, j) // such that arr[i] * arr[j] = arr[i] + arr[j] static long countPairs(int arr[], int n) { int countZero = 0; int countTwo = 0; // Count number of 0's and 2's in the array for (int i = 0; i < n; i++) { if (arr[i] == 0) countZero++; else if (arr[i] == 2) countTwo++; } // Total pairs due to occurrence of 0's long pair0 = (countZero * (countZero - 1)) / 2; // Total pairs due to occurrence of 2's long pair2 = (countTwo * (countTwo - 1)) / 2; // Return count of all pairs return pair0 + pair2; } // Driver code public static void main(String[] args) { int arr[] = { 2, 0, 3, 2, 0 }; int n = arr.length; // Get and print count of pairs System.out.println(countPairs(arr, n)); }} |
Python3
# Python3 program to count pairs (i, j) # such that arr[i] * arr[j] = arr[i] + arr[j] # Function to return the count of pairs(i, j) # such that arr[i] * arr[j] = arr[i] + arr[j] def countPairs(arr, n): countZero = 0; countTwo = 0; # Count number of 0's and 2's in the array for i in range(n) : if (arr[i] == 0) : countZero += 1; elif (arr[i] == 2) : countTwo += 1; # Total pairs due to occurrence of 0's pair0 = (countZero * (countZero - 1)) // 2; # Total pairs due to occurrence of 2's pair2 = (countTwo * (countTwo - 1)) // 2; # Return count of all pairs return pair0 + pair2; # Driver code if __name__ == "__main__" : arr = [ 2, 0, 3, 2, 0 ]; n = len(arr); # Get and print count of pairs print(countPairs(arr, n)); # This code is contributed by AnkitRai01 |
C#
// C# program to count pairs (i, j)// such that arr[i] * arr[j] = arr[i] + arr[j]using System;class GFG { // Function to return the count of pairs(i, j) // such that arr[i] * arr[j] = arr[i] + arr[j] static long countPairs(int[] arr, int n) { int countZero = 0; int countTwo = 0; // Count number of 0's and 2's in the array for (int i = 0; i < n; i++) { if (arr[i] == 0) countZero++; else if (arr[i] == 2) countTwo++; } // Total pairs due to occurrence of 0's long pair0 = (countZero * (countZero - 1)) / 2; // Total pairs due to occurrence of 2's long pair2 = (countTwo * (countTwo - 1)) / 2; // Return count of all pairs return pair0 + pair2; } // Driver code public static void Main(string[] args) { int[] arr = { 2, 0, 3, 2, 0 }; int n = arr.Length; // Get and print count of pairs Console.WriteLine(countPairs(arr, n)); }} |
Output:
2
Time Complexity: O(n)
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!
<!–
–>
Count pairs (i, j) from an array such that |arr[i]| and |arr[j]| both lies between |arr[i] – arr[j]| and |arr[i] + arr[j]|
Count number of pairs (i, j) such that arr[i] * arr[j] > arr[i] + arr[j]
Count the number of pairs (i, j) such that either arr[i] is divisible by arr[j] or arr[j] is divisible by arr[i]
Count of pairs {X, Y} from an array such that sum of count of set bits in X ⊕ Y and twice the count of set bits in X & Y is M
Count ways to remove pairs from a matrix such that remaining elements can be grouped in vertical or horizontal pairs
Maximize count of pairs whose Bitwise AND exceeds Bitwise XOR by replacing such pairs with their Bitwise AND
Maximize count of pairs whose bitwise XOR is even by replacing such pairs with their Bitwise XOR
Maximum count of pairs such that element at each index i is included in i pairs
Count pairs in an array such that LCM(arr[i], arr[j]) > min(arr[i],arr[j])
Count of pairs (arr[i], arr[j]) such that arr[i] + j and arr[j] + i are equal
Mathematical and Geometric Algorithms – Data Structure and Algorithm Tutorials
Learn Data Structures with Javascript | DSA Tutorial
Introduction to Max-Heap – Data Structure and Algorithm Tutorials
Introduction to Set – Data Structure and Algorithm Tutorials
Introduction to Map – Data Structure and Algorithm Tutorials
Please Login to comment…