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

Given two arrays X[] and Y[] of positive integers, find a 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
Explanation: 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
Explanation: 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.

Following code based on brute force solution.

• C++

`long` `long` `countPairsBruteForce(` `long` `long` `X[], ` `long` `long` `Y[],`

` ` `long` `long` `m, ` `long` `long` `n)`

`{`

` ` `long` `long` `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;`

`}`

Time Complexity: O(M*N) where M and N are sizes of given arrays.

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.

• Sort array Y[].
• For every x in X[], find the index idx of the 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.
• 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[].
• x smaller than y means x^y is greater than y^x.
1. x = 2, y = 3 or 4
2. x = 3, y = 2

Note that the case where x = 4 and y = 2 is not there

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.

Below is the implementation of the above approach:

• C++

`// C++ program to finds the number of pairs (x, y)`

`// in an array such that x^y > y^x`

`#include <bits/stdc++.h>`

`using` `namespace` `std;`

`// Function to 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;`

`}`

`// Function to return 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`

`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: O(nLogn + mLogn), where m and n are 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.