Home » Data Structure » Array Data Structure

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

Last Updated : April 19, 2025

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

Find the number of pairs(x, y) in an array using 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.

Find the number of pairs(x, y) in an array using 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.