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

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.

• JAVA

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

` ` `int` `m, ` `int` `n)`

`{`

` ` `long` `ans = ` `0` `;`

` ` `for` `(` `int` `i = ` `0` `; i < m; i++)`

` ` `for` `(` `int` `j = ` `0` `; j < n; j++)`

` ` `if` `(Math.pow(X[i], Y[j]) > Math.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:

• JAVA

`// Java program to finds number of pairs (x, y)`

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

`import` `java.util.Arrays;`

`class` `Test {`

` ` `// 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`

` ` `static` `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 getting upperbound of x with`

` ` `// binary search`

` ` `int` `idx = Arrays.binarySearch(Y, x);`

` ` `int` `ans;`

` ` `if` `(idx < ` `0` `) {`

` ` `idx = Math.abs(idx + ` `1` `);`

` ` `ans = Y.length - idx;`

` ` `}`

` ` `else` `{`

` ` `while` `(idx < n && Y[idx] == x) {`

` ` `idx++;`

` ` `}`

` ` `ans = Y.length - 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 returns count of pairs (x, y) such that`

` ` `// x belongs to X[], y belongs to Y[] and x^y > y^x`

` ` `static` `long` `countPairs(` `int` `X[], ` `int` `Y[], ` `int` `m, ` `int` `n)`

` ` `{`

` ` `// To store counts of 0, 1, 2, 3 and 4 in array Y`

` ` `int` `NoOfY[] = ` `new` `int` `[` `5` `];`

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

` ` `Arrays.sort(Y);`

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

` ` `public` `static` `void` `main(String args[])`

` ` `{`

` ` `int` `X[] = { ` `2` `, ` `1` `, ` `6` `};`

` ` `int` `Y[] = { ` `1` `, ` `5` `};`

` ` `System.out.println(`

` ` `"Total pairs = "`

` ` `+ countPairs(X, Y, X.length, Y.length));`

` ` `}`

`}`

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.