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.
- C++
long long countPairsBruteForce( long long X[], long long Y[],
long long m, long long n)
{
long long 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;
}
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:
- C++
// C++ program to finds the number of pairs (x, y)
// in an array such that x^y > y^x
#include <bits/stdc++.h>
using namespace std;
// 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
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;
}
// Function to return 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;
}
// Driver program
int main()
{
int X[] = { 2, 1, 6 };
int Y[] = { 1, 5 };
int m = sizeof (X) / sizeof (X[0]);
int n = sizeof (Y) / sizeof (Y[0]);
cout << "Total pairs = " << countPairs(X, Y, m, n);
return 0;
}
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.