Home » Data Structure » Array Data Structure

Find the number of pairs(x, y) in an array such that x^y > y^x

C++ implementation to find the number of pairs(x, y) in an array such that x^y > y^x.
Submitted by Vikneshwar GK, on February 06, 2022

Consider 2 arrays X and Y, containing positive integers. The task at hand is to find the number of pairs that satisfies the condition X[i]^Y[j] > Y[j]^X[i]. A pair contains an element from array X and another element from array Y.

Example:

Input:
array1[] = {2, 1, 6}
array2[] = {1, 5}

Output:
Number of pairs: 3

Explanation:
Only the pair (2, 1), (2, 5), and (6, 1) 
satisfies the given condition

Input:
array1[] = {10, 19, 18}
array2[] = {11, 15, 9}

Output:
Number of pairs: 2	

Explanation:
Only the pair (10, 11), and (10, 15) 
satisfies the given condition

Solution 1: Brute force

This is the simple straightforward approach, that is, to use a nested loop and iterate through both the arrays and find the pair that satisfies the given condition. If it satisfies, increment the counter.

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

int countPairs(int array1[], int array2[], int length1, int length2)
{
    int count = 0;

    for (int i = 0; i < length1; i++)
        for (int j = 0; j < length2; j++)
            if (pow(array1[i], array2[j]) > pow(array2[j], array1[i]))
                count++;
    return count;
}

// Main function
int main()
{
    int array1[100], array2[100], length1, length2;
    
    cout << "Enter Number of elements for array 1: ";
    cin >> length1;

    for (int i = 0; i < length1; i++) {
        cout << "Enter element " << i + 1 << ":";
        cin >> array1[i];
    }

    cout << "Enter Number of elements for array 2: ";
    cin >> length2;

    for (int j = 0; j < length2; j++) {
        cout << "Enter element " << j + 1 << ":";
        cin >> array2[j];
    }

    cout << "Number of pairs: " << countPairs(array1, array2, length1, length2);

    return 0;
}

Output:

Enter Number of elements for array 1: 3
Enter element 1:2
Enter element 2:1
Enter element 3:6
Enter Number of elements for array 2: 2
Enter element 1:1
Enter element 2:5
Number of pairs: 3

Time Complexity: O(m*n), where m and n are the lengths of the array.

Solution 2: Sort and Search

This is an efficient solution that involves sorting array2. The underlying concept here is that, if y>x then x^y > y^x. This holds true except for certain exceptions. 

• Sort array2
• For every item in array1, find the smallest element in array2 such that array1 element is lesser than that array2 element and note the index
• Every item after that array 2 element will satisfy the given condition, hence adding their count

Need to know:

• If array1[i] is 0, then there is no pair for this element
• If array1[i] is 1, then the count of pair is the number of 0s in array2
• If x<y, it satisfies x^y > y^x except when array1[i]=2 and array2[i]=3,4 and array1[i] = 3 and array2[i] = 2

In order to handle the exception cases, we can count the number of 0, 1, 2, 3, and 4 in the array2 before starting the algorithm. In this way, we can handle the exceptional case in constant time.

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

//  Function to count the pair
int count(int element, int array2[], int length2, int yException[])
{
    // If array1 element is 0
    // then there are no pairs for this element
    if (element == 0)
        return 0;

    // If array1 element is 1
    // then return number of zeros in array2
    if (element == 1)
        return yException[0];

    // Find the min element index in array2
    // that is greater than element
    int* index = upper_bound(array2, array2 + length2, element);
    int count = (array2 + length2) - index;

    // update count
    count += (yException[0] + yException[1]);

    // Decrease number of pairs for x=2 and (y=4 or y=3)
    if (element == 2)
        count -= (yException[3] + yException[4]);

    // Increase number of pairs for x=3 and y=2
    if (element == 3)
        count += yException[2];

    return count;
}

// Function to sort, preprocess array2 and return pair count
int countPairs(int array1[], int array2[], int length1, int length2)
{
    // To store counts of 0, 1, 2, 3 and 4 in array Y
    int yException[5] = { 0 };
    for (int i = 0; i < length2; i++)
        if (yException[i] < 5)
            yException[array2[i]]++;

    // sort array2
    sort(array2, array2 + length2);

    int total_pairs = 0; // Initialize result

    // Take every element of array1 and count pairs with it
    for (int i = 0; i < length1; i++)
        total_pairs += count(array1[i], array2, length2, yException);

    return total_pairs;
}

// main function
int main()
{
    int array1[100], array2[100], length1, length2;
    cout << "Enter Number of elements for array 1: ";
    cin >> length1;

    for (int i = 0; i < length1; i++) {
        cout << "Enter element " << i + 1 << ":";
        cin >> array1[i];
    }

    cout << "Enter Number of elements for array 2: ";
    cin >> length2;

    for (int j = 0; j < length2; j++) {
        cout << "Enter element " << j + 1 << ":";
        cin >> array2[j];
    }

    cout << "Number of pairs: " << countPairs(array1, array2, length1, length2);

    return 0;
}

Output:

Enter Number of elements for array 1: 3
Enter element 1:2
Enter element 2:1
Enter element 3:6
Enter Number of elements for array 2: 2
Enter element 1:1
Enter element 2:5
Number of pairs: 3

Time Complexity: O(nlog(n) + mlog(n)), where m and n are lengths of array1 and array2 respectively.