Find number of pairs such that x^y > y^x

Given two arrays X[] and Y[] of positive integers, find number of pairs such that x^y > y^x where x is an element from X[] and y is an element from Y[].

Examples:

  Input: X[] = {2, 1, 6}, Y = {1, 5}
  Output: 3 
  // There are total 3 pairs where pow(x, y) is greater than pow(y, x)
  // Pairs are (2, 1), (2, 5) and (6, 1)


  Input: X[] = {10, 19, 18}, Y[] = {11, 15, 9};
  Output: 2
  // There are total 2 pairs where pow(x, y) is greater than pow(y, x)
  // Pairs are (10, 11) and (10, 15)

The brute force solution is to consider each element of X[] and Y[], and check whether the given condition satisfies or not. Time Complexity of this solution is O(m*n) where m and n are sizes of given arrays.

Following is C++ code based on brute force solution.

int countPairsBruteForce(int X[], int Y[], int m, int n) {     int ans = 0;     for (int i = 0; i < m; i++)        for (int j = 0; j < n; j++)           if (pow(X[i], Y[j]) > pow(Y[j], X[i]))               ans++;     return ans; }

Efficient Solution: 
The problem can be solved in O(nLogn + mLogn) time. The trick here is, if y > x then x^y > y^x with some exceptions. Following are simple steps based on this trick.

1) Sort array Y[].
2) For every x in X[], find the index idx of smallest number greater than x (also called ceil of x) in Y[] using binary search or we can use the inbuilt function upper_bound() in algorithm library.
3) All the numbers after idx satisfy the relation so just add (n-idx) to the count.

Base Cases and Exceptions:
Following are exceptions for x from X[] and y from Y[]
If x = 0, then the count of pairs for this x is 0.
If x = 1, then the count of pairs for this x is equal to count of 0s in Y[].
The following cases must be handled separately as they don’t follow the general rule that x smaller than y means x^y is greater than y^x.
a) x = 2, y = 3 or 4
b) x = 3, y = 2
Note that the case where x = 4 and y = 2 is not there

Following diagram shows all exceptions in tabular form. The value 1 indicates that the corresponding (x, y) form a valid pair.

Following is C++ implementation. In the following implementation, we pre-process the Y array and count 0, 1, 2, 3 and 4 in it, so that we can handle all exceptions in constant time. The array NoOfY[] is used to store the counts.

#include<iostream> #include<algorithm> using namespace std;   // This function return count of pairs with x as one element // of the pair. It mainly looks for all values in Y[] where // x ^ Y[i] > Y[i] ^ x int count(int x, int Y[], int n, int NoOfY[]) {     // If x is 0, then there cannot be any value in Y such that     // x^Y[i] > Y[i]^x     if (x == 0) return 0;       // If x is 1, then the number of pais is equal to number of     // zeroes in Y[]     if (x == 1) return NoOfY[0];       // Find number of elements in Y[] with values greater than x     // upper_bound() gets address of first greater element in Y[0..n-1]     int* idx = upper_bound(Y, Y + n, x);     int ans = (Y + n) - idx;       // If we have reached here, then x must be greater than 1,     // increase number of pairs for y=0 and y=1     ans += (NoOfY[0] + NoOfY[1]);       // Decrease number of pairs for x=2 and (y=4 or y=3)     if (x == 2)  ans -= (NoOfY[3] + NoOfY[4]);       // Increase number of pairs for x=3 and y=2     if (x == 3)  ans += NoOfY[2];       return ans; }   // The main function that returns count of pairs (x, y) such that // x belongs to X[], y belongs to Y[] and x^y > y^x int countPairs(int X[], int Y[], int m, int n) {     // To store counts of 0, 1, 2, 3 and 4 in array Y     int NoOfY[5] = {0};     for (int i = 0; i < n; i++)         if (Y[i] < 5)             NoOfY[Y[i]]++;       // Sort Y[] so that we can do binary search in it     sort(Y, Y + n);       int total_pairs = 0; // Initialize result       // Take every element of X and count pairs with it     for (int i=0; i<m; i++)         total_pairs += count(X[i], Y, n, NoOfY);       return total_pairs; }   // Driver program to test above functions int main() {     int X[] = {2, 1, 6};     int Y[] = {1, 5};       int m = sizeof(X)/sizeof(X[0]);     int n = sizeof(Y)/sizeof(Y[0]);       cout << "Total pairs = " << countPairs(X, Y, m, n);       return 0; }

Output:

Total pairs = 3

Time Complexity : Let m and n be the sizes of arrays X[] and Y[] respectively. The sort step takes O(nLogn) time. Then every element of X[] is searched in Y[] using binary search. This step takes O(mLogn) time. Overall time complexity is O(nLogn + mLogn).