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.
- x = 2, y = 3 or 4
- 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.