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.