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

Find number of pairs (x, y) in an array such that x^y > y^x - GeeksforGeeks
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[].

  Input: X[] = {2, 1, 6}, Y = {1, 5}
  Output: 3 
  // There are total 3 pairs where pow(x, y) is greater than pow(y, x)
  // Pairs are (2, 1), (2, 5) and (6, 1)

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.

1) Sort array Y[].
2) For every x in X[], find the index idx of 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.
3) 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[].
The following cases must be handled separately as they don’t follow the general rule that x smaller than y means x^y is greater than y^x.
a) x = 2, y = 3 or 4
b) x = 3, y = 2
Note that the case where x = 4 and y = 2 is not there

Following diagram shows all exceptions in tabular form. The value 1 indicates that the corresponding (x, y) form a valid pair.

Following is C++ implementation. 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.

// 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

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;

}

 

// The main function that returns 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;

}

http://www.geeksforgeeks.org/find-number-pairs-xy-yx/
    public int countPairs(int X[],int Y[]){
        Map<Integer,Integer> hardCoded = new HashMap<Integer,Integer>();
        for(int i=0; i < Y.length; i++){
            if(Y[i] < 4){
                Integer count = hardCoded.get(Y[i]);
                if(count != null){
                    hardCoded.put(Y[i], count++);
                }else{
                    hardCoded.put(Y[i], 1);
                }
            }
        }
        Arrays.sort(Y);
        int countPairs = 0;
        for(int i=0 ; i < X.length; i++){
            countPairs += count(X[i],Y,hardCoded);
        }
        return countPairs;
    }
   
    private int count(int x, int Y[],Map<Integer,Integer> hardCount){
       
        if(x == 0){
            return 0;
        }
        if(x == 1){
            return upperBound(0,Y);
        }
        int result = Y.length - upperBound(x,Y);
        result +=  (hardCount.containsKey(1) ? hardCount.get(1) : 0 ) + (hardCount.containsKey(0) ? hardCount.get(0) : 0);
   
        if(x == 2){
            result -= (hardCount.containsKey(3)  ? hardCount.get(3) : 0);
        }
        if(x == 3){
            result += (hardCount.containsKey(2)  ? hardCount.get(2) : 0);
        }
        return result;
    }
   
    private int upperBound(int x, int arr[]){
        int low = 0;
        int high = arr.length-1;
        while(low <= high){
            int mid = (low+high)/2;
            if(arr[mid] > x && (mid-1 < 0 || arr[mid-1] <= x)){
                return mid;
            }else if(arr[mid] > x){
                high = mid-1;
            }else{
                low = mid+1;
            }
        }
        return -1;
       
    }

The brute force solution is to consider each element of X[] and Y[], and check whether the given condition satisfies or not. Time Complexity of this solution is O(m*n) where m and n are sizes of given arrays.

int countPairsBruteForce(int X[], int Y[], int m, int n)

{

    int 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;

}

Read full article from Find number of pairs (x, y) in an array such that x^y > y^x - GeeksforGeeks