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.