Number of pairs

Given two positive integer arrays arr and brr, find the number of pairs such that x^y > y^x (raised to power of) where x is an element from arr and y is an element from brr.

Examples :

Input: arr[] = [2, 1, 6], brr[] = [1, 5]
Output: 3
Explanation: The pairs which follow xy > yx are: 21 > 12,  25 > 52 and 61 > 16 .

Input: arr[] = [2 3 4 5], brr[] = [1 2 3]
Output: 5
Explanation: The pairs which follow xy > yx are: 21 > 12 , 31 > 13 , 32 > 23 , 41 > 14 , 51 > 15 .

Expected Time Complexity: O((N + M)log(N)).
Expected Auxiliary Space: O(1).

Constraints:
1 ≤ arr.size(), brr.size() ≤ 10⁵
1 ≤ brr[i], arr[i] ≤ 10³

Approach 01:

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iterator>

class Solution {
  public:
    long long countPairs(std::vector<int> &arr, std::vector<int> &brr) {
        std::vector<double> arrLogRatios, brrLogRatios;

        // Calculate log(x)/x for each element in arr
        for (int x : arr) {
            arrLogRatios.push_back(std::log(x) / x);
        }

        // Calculate log(y)/y for each element in brr
        for (int y : brr) {
            brrLogRatios.push_back(std::log(y) / y);
        }

        // Sort the ratios
        std::sort(arrLogRatios.begin(), arrLogRatios.end());
        std::sort(brrLogRatios.begin(), brrLogRatios.end());

        long long pairCount = 0;

        // Count pairs using lower_bound to find the appropriate index in brrLogRatios
        for (double arrRatio : arrLogRatios) {
            auto index = std::lower_bound(brrLogRatios.begin(), brrLogRatios.end(), arrRatio);
            pairCount += std::distance(brrLogRatios.begin(), index);
        }

        return pairCount;
    }
};

import math
import bisect

class Solution:
    
    def countPairs(self, arr, brr):
        arrLogRatios = []
        brrLogRatios = []

        # Calculate log(x)/x for each element in arr
        for x in arr:
            arrLogRatios.append(math.log(x) / x)

        # Calculate log(y)/y for each element in brr
        for y in brr:
            brrLogRatios.append(math.log(y) / y)

        # Sort the ratios
        arrLogRatios.sort()
        brrLogRatios.sort()

        pairCount = 0

        # Count pairs using bisect_left to find the appropriate index in brrLogRatios
        for arrRatio in arrLogRatios:
            index = bisect.bisect_left(brrLogRatios, arrRatio)
            pairCount += index

        return pairCount

Time Complexity

• Logarithmic Ratio Calculation:

  Calculating \( \log(x)/x \) for each element in the arrays arr and brr takes \( O(n) \) and \( O(m) \) time, respectively, where \( n \) and \( m \) are the sizes of arr and brr.

• Sorting:

  Sorting the ratios for both arrays takes \( O(n \log n) \) for arrLogRatios and \( O(m \log m) \) for brrLogRatios.

• Pair Counting:

  For each element in arrLogRatios, we perform a binary search using std::lower_bound on brrLogRatios, which takes \( O(\log m) \) time. Since this operation is repeated for all \( n \) elements, the total time complexity for this step is \( O(n \log m) \).

• Overall Time Complexity:

  The overall time complexity is \( O(n \log n + m \log m + n \log m) \).

Space Complexity

• Auxiliary Space:

  The auxiliary space is used for storing the logarithmic ratios, which requires \( O(n + m) \) space.

• Overall Space Complexity:

  The overall space complexity is \( O(n + m) \), dominated by the space required to store the logarithmic ratios.