JavaScript Program to Find Number Pairs (x, y) in an Array Such That x^y > y^x
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)
Table of Content
- Using Naive Approach
- Using Binary Search
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));
Output
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));
Output
Number of pairs: 5
Time Complexity: O(nlogn + mlogm) Here, n and m are the size of array
Space Complexity: O(1)