## Saturday, December 5, 2015

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

Find number of pairs (x, y) in an array such that x^y > y^x - GeeksforGeeks
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[].

```  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)
```
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.
`// 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;`
`}`

http://www.geeksforgeeks.org/find-number-pairs-xy-yx/
public int countPairs(int X[],int Y[]){
Map<Integer,Integer> hardCoded = new HashMap<Integer,Integer>();
for(int i=0; i < Y.length; i++){
if(Y[i] < 4){
Integer count = hardCoded.get(Y[i]);
if(count != null){
hardCoded.put(Y[i], count++);
}else{
hardCoded.put(Y[i], 1);
}
}
}
Arrays.sort(Y);
int countPairs = 0;
for(int i=0 ; i < X.length; i++){
countPairs += count(X[i],Y,hardCoded);
}
return countPairs;
}

private int count(int x, int Y[],Map<Integer,Integer> hardCount){

if(x == 0){
return 0;
}
if(x == 1){
return upperBound(0,Y);
}
int result = Y.length - upperBound(x,Y);
result +=  (hardCount.containsKey(1) ? hardCount.get(1) : 0 ) + (hardCount.containsKey(0) ? hardCount.get(0) : 0);

if(x == 2){
result -= (hardCount.containsKey(3)  ? hardCount.get(3) : 0);
}
if(x == 3){
result += (hardCount.containsKey(2)  ? hardCount.get(2) : 0);
}
return result;
}

private int upperBound(int x, int arr[]){
int low = 0;
int high = arr.length-1;
while(low <= high){
int mid = (low+high)/2;
if(arr[mid] > x && (mid-1 < 0 || arr[mid-1] <= x)){
return mid;
}else if(arr[mid] > x){
high = mid-1;
}else{
low = mid+1;
}
}
return -1;

}
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.
`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;`
`}`
Read full article from Find number of pairs (x, y) in an array such that x^y > y^x - GeeksforGeeks