Given two arrays A[] and B[] of sizes N and M respectively, we need to find the count of pairs (x, y) such that x^y > y^x. Here, x is an element of array A[] whereas y is an element of array B[].

Example:

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)

Using Naive Approach

This approach employs a naive method to find pairs (x, y) in arrays A and B such that x^y > y^x. It iterates through all possible pairs of elements from arrays A and B and compares their powers using nested loops. If the condition x^y > y^x holds true for a pair, the count variable is incremented.

Approach:

• Start by initializing a count variable to keep track of the number of pairs that satisfy the condition.
• Iterate through each element of array A and array B using nested loops.
• For each pair (x, y), calculate the powers x^y and y^x using the Math.pow() function.
• If x^y is greater than y^x, increment the count variable to indicate that the pair satisfies the condition.
• After checking all pairs, return the final count of pairs that satisfy the condition.

Example: Implementation to find number of pairs (x, y) in an array such that x^y > y^x using naive approach.

function countPairs(A, B) {
    let count = 0;
    for (let i = 0; i < A.length; ++i) {
        for (let j = 0; j < B.length; ++j) {
            if (Math.pow(A[i], B[j]) > Math.pow(B[j], A[i])) {
                count++;
            }
        }
    }
    return count;
}

const A = [1, 2, 3];
const B = [4, 5, 6];
console.log("Number of pairs:", countPairs(A, B)); 

Number of pairs: 5

Time Complexity: O(n*m) Here, n and m are the size of array

Space Complexity: O(1)

Using Binary Search

This approach utilizes binary search and frequency counting to find pairs (x, y) in arrays A and B such that x^y > y^x. It first sorts array B and then calculates the frequency of elements in B[]. For each element x in array A[], it uses binary search to find the index of the smallest element greater than x in B[]. Based on the value of x and the frequencies of elements in B[], it calculates the count of pairs that satisfy the condition x^y > y^x.

Approach:

• Create a frequency array to count the occurrences of elements 0, 1, 2, 3, 4 in array B[].
• Sort array B[] in ascending order to facilitate binary search.
• Iterate through array B[] and count the frequency of elements less than 5.
• Define a function count(x, B, freq) to calculate the count of pairs for a given element x and frequency array freq in array B[].
• For each element x in array A[], use binary search to find the index of the smallest element greater than x in array B[].
• Based on the value of x and the frequencies of elements in B[], calculate the count of pairs that satisfy the condition x^y > y^x.
• Sum up the counts obtained for each element in array A[] to get the total number of pairs that satisfy the condition.

Example: Implementation to find number of pairs (x, y) in an array such that x^y > y^x using binary search approach.

function count(x, B, freq) {
    if (x === 0)
        return 0;

    if (x === 1)
        return freq[0];

    const ind = B.findIndex(num => num > x);
    let count = B.length - ind;

    count += freq[0] + freq[1];

    if (x === 2)
        count -= freq[3] + freq[4];

    if (x === 3)
        count += freq[2];

    return count;
}

function countPairs(A, B) {
    const freq = new Array(5).fill(0);
    B.forEach(num => {
        if (num < 5)
            freq[num]++;
    });

    B.sort((a, b) => a - b);

    let totalPairs = 0;

    A.forEach(x => {
        totalPairs += count(x, B, freq);
    });

    return totalPairs;
}
const A = [1, 2, 3];
const B = [4, 5, 6];
console.log("Number of pairs:", countPairs(A, B)); 

Number of pairs: 5

Time Complexity: O(nlogn + mlogm) Here, n and m are the size of array

Space Complexity: O(1)