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

C++ implementation to find the number of pairs(x, y) in an array such that x^y > y^x.
Submitted by Vikneshwar GK, on February 06, 2022

Consider 2 arrays X and Y, containing positive integers. The task at hand is to find the number of pairs that satisfies the condition X[i]^Y[j] > Y[j]^X[i]. A pair contains an element from array X and another element from array Y.

Example:

```Input:
array1[] = {2, 1, 6}
array2[] = {1, 5}

Output:
Number of pairs: 3

Explanation:
Only the pair (2, 1), (2, 5), and (6, 1)
satisfies the given condition

Input:
array1[] = {10, 19, 18}
array2[] = {11, 15, 9}

Output:
Number of pairs: 2

Explanation:
Only the pair (10, 11), and (10, 15)
satisfies the given condition
```

Solution 1: Brute force

This is the simple straightforward approach, that is, to use a nested loop and iterate through both the arrays and find the pair that satisfies the given condition. If it satisfies, increment the counter.

## C++ Implementation

```#include <bits/stdc++.h>
using namespace std;

int countPairs(int array1[], int array2[], int length1, int length2)
{
int count = 0;

for (int i = 0; i < length1; i++)
for (int j = 0; j < length2; j++)
if (pow(array1[i], array2[j]) > pow(array2[j], array1[i]))
count++;
return count;
}

// Main function
int main()
{
int array1[100], array2[100], length1, length2;

cout << "Enter Number of elements for array 1: ";
cin >> length1;

for (int i = 0; i < length1; i++) {
cout << "Enter element " << i + 1 << ":";
cin >> array1[i];
}

cout << "Enter Number of elements for array 2: ";
cin >> length2;

for (int j = 0; j < length2; j++) {
cout << "Enter element " << j + 1 << ":";
cin >> array2[j];
}

cout << "Number of pairs: " << countPairs(array1, array2, length1, length2);

return 0;
}
```

Output:

```Enter Number of elements for array 1: 3
Enter element 1:2
Enter element 2:1
Enter element 3:6
Enter Number of elements for array 2: 2
Enter element 1:1
Enter element 2:5
Number of pairs: 3
```

Time Complexity: O(m*n), where m and n are the lengths of the array.

Solution 2: Sort and Search

This is an efficient solution that involves sorting array2. The underlying concept here is that, if y>x then x^y > y^x. This holds true except for certain exceptions.

• Sort array2
• For every item in array1, find the smallest element in array2 such that array1 element is lesser than that array2 element and note the index
• Every item after that array 2 element will satisfy the given condition, hence adding their count

Need to know:

• If array1[i] is 0, then there is no pair for this element
• If array1[i] is 1, then the count of pair is the number of 0s in array2
• If x<y, it satisfies x^y > y^x except when array1[i]=2 and array2[i]=3,4 and array1[i] = 3 and array2[i] = 2

In order to handle the exception cases, we can count the number of 0, 1, 2, 3, and 4 in the array2 before starting the algorithm. In this way, we can handle the exceptional case in constant time.

C++ Implementation:

```#include <bits/stdc++.h>
using namespace std;

//  Function to count the pair
int count(int element, int array2[], int length2, int yException[])
{
// If array1 element is 0
// then there are no pairs for this element
if (element == 0)
return 0;

// If array1 element is 1
// then return number of zeros in array2
if (element == 1)
return yException[0];

// Find the min element index in array2
// that is greater than element
int* index = upper_bound(array2, array2 + length2, element);
int count = (array2 + length2) - index;

// update count
count += (yException[0] + yException[1]);

// Decrease number of pairs for x=2 and (y=4 or y=3)
if (element == 2)
count -= (yException[3] + yException[4]);

// Increase number of pairs for x=3 and y=2
if (element == 3)
count += yException[2];

return count;
}

// Function to sort, preprocess array2 and return pair count
int countPairs(int array1[], int array2[], int length1, int length2)
{
// To store counts of 0, 1, 2, 3 and 4 in array Y
int yException[5] = { 0 };
for (int i = 0; i < length2; i++)
if (yException[i] < 5)
yException[array2[i]]++;

// sort array2
sort(array2, array2 + length2);

int total_pairs = 0; // Initialize result

// Take every element of array1 and count pairs with it
for (int i = 0; i < length1; i++)
total_pairs += count(array1[i], array2, length2, yException);

}

// main function
int main()
{
int array1[100], array2[100], length1, length2;
cout << "Enter Number of elements for array 1: ";
cin >> length1;

for (int i = 0; i < length1; i++) {
cout << "Enter element " << i + 1 << ":";
cin >> array1[i];
}

cout << "Enter Number of elements for array 2: ";
cin >> length2;

for (int j = 0; j < length2; j++) {
cout << "Enter element " << j + 1 << ":";
cin >> array2[j];
}

cout << "Number of pairs: " << countPairs(array1, array2, length1, length2);

return 0;
}
```

Output:

```Enter Number of elements for array 1: 3
Enter element 1:2
Enter element 2:1
Enter element 3:6
Enter Number of elements for array 2: 2
Enter element 1:1
Enter element 2:5
Number of pairs: 3
```

Time Complexity: O(nlog(n) + mlog(n)), where m and n are lengths of array1 and array2 respectively.