Tip:
Highlight text to annotate it
X
Hi friends and welcome to GeeksforGeeks. In this tutorial, we will learn how to find number
of pairs in an array such that x^y > y^x. So, here’s the problem. 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[].
Let’s look at an example where and x is this and y is this. So for this input, the
output is 3. The pairs for which this condition is applicable are (2, 1), (2, 5) and (6, 1)
The brute force solution is to consider each element of X[] and Y[], and check whether
the given condition satisfies or not. Here’s the implementation of this problem in c++.
Let’s look at a better solution to this problem. First, we sort array Y. Now, for
every element x in array X, we find the index of smallest number greater than x in the array
Y. We can do this using binary search or inbuilt function, upper_bound(). All the numbers after
this index satisfies the relation so we add (size of array Y(n) - that index) to the count.
These are a few exceptions. If x = 0, then the count of pairs for this x is 0. If x = 1,
then the count of pairs is just the number of 0s in Y. The following cases must be handled
separately as they do not follow the general rule that x smaller than y means, x^y is greater
than y^x. These cases include, x = 2 and y = 3 or 4 because 2^3 i.e 8 is smaller than
3^2 i.e. 9 and 2^4 is equal to 4^2. This table shows all the exceptions. We can
see that at x = 0 and any value of y, the relation is not applicable, so we have 0 in
those slots. 1 represents that the relation is valid and 0 represents relation being invalid.
At x = 1 and y = 0, relation is applicable, so we have 1. And so on this table shows results
for all values of x and y where the general algorithm is not applicable.
Let’s implement our algorithm on this example. We can see that, y is already sorted. Starting
with x = 2, we need to find elements in y that satisfies the given condition. From the
previous table, we can see that x = 2 and y = 1 satisfies the condition. Now, upper
bound of 2 in y is 5, which has the index 1. So, the number of pairs that satisfy the
given condition for x = 2 are 2. The pairs are (2,1) and (2,5). Next, x = 1 does not
satisfy this condition for any value of y. Next, x = 6 satisfies this equation for y
= 1. So, the number of pairs that satisfy the given condition for x = 6 is 1. Pairs:
{(6,1)} So, the output is 2 + 1 = 3 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. If x is 0, we return 0. If x = 1, we return the number of 0s in Y. Else, we find
find the upper bound and count using this statement. Here we are checking for the exceptions
we discussed in the table. This function counts the total number of pairs.
First, we store the count of 0,1,2,3 and 4 which have exceptions. Then, we sort the array
Y according to our algaorithm. At last we count the pairs for all values of x using
a simple for loop and the function we just discussed.
Let m and n be 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(m Logn) time. Overall time complexity is O(nLogn + mLogn).
This brings us to the end of this tutorial, thank you for watching! Please leave us your
likes and comments in the comments section.