Tutorialspoint.dev

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

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[].

Examples:

  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)


  Input: X[] = {10, 19, 18}, Y[] = {11, 15, 9};
  Output: 2
  // 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. Time Complexity of this solution is O(m*n) where m and n are sizes of given arrays.

Following is C++ code based on brute force solution.

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

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.



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.
exception table

Following is 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.

C++

// Java program to finds number of pairs (x, y)
// in an array such that x^y > y^x
  
#include<iostream>
#include<algorithm>
using namespace std;
  
// 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;
}
  
// Driver program to test above functions
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;
}

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
{
    // 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
    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 (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;
    }
       
    // 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
    static 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[] = 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);
       
        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 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));
    }
}

C#

// C# program to finds number of pairs (x, y)
// in an array such that x^y > y^x
using System;
  
class GFG {
      
    // 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
    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 = Array.BinarySearch(Y, x);
        int ans;
        if (idx < 0) {
            idx = Math.Abs(idx + 1);
            ans = Y.Length - idx;
        }
          
        else {
            while (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;
    }
  
    // 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
    static 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 = 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
        Array.Sort(Y);
  
        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 method
    public static void Main()
    {
        int[] X = { 2, 1, 6 };
        int[] Y = { 1, 5 };
  
        Console.Write("Total pairs = "
                       countPairs(X, Y, X.Length, Y.Length));
    }
}
  
// This code is contributed by Sam007


Output:

Total pairs = 3

Time Complexity : 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(mLogn) time. Overall time complexity is O(nLogn + mLogn).



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter