Find number of pairs (x, y) in an array such that x^y > y^x using JAVA

Software Development
#1

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.
    1. x = 2, y = 3 or 4
    2. 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.