Count number of pairs (i, j) such that arr[i] * arr[j] = arr[i] + arr[j]

0 0 8 minutes read

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 code
int 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 satisfy
if (arr[i] * arr[j] == arr[i] + arr[j])
count++;
}
}
 
// Return count of pairs
return 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:

Time Complexity: O(n²)
Auxiliary Space: O(1²)

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 code
int 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:

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 zambiatek!

Last Updated :
30 Mar, 2022