## Problem Statement

Given two integer arrays **A[]** and **B[]** of size **N** and **M** respectively. The task is to count the number of pairs (**x, y)** such that **x^y > y^x**, where **x **is an element of array **A[]**, while **y** is an element of array **B[]**.

**Examples:**

**Input: **A[] = {2, 1, 6}, B[] = {1, 5}**Output: **3**Explanation:**

There are three possible pairs :

- (2, 1) : 2 ^ 1 > 1 ^ 2
- (6, 1) : 6 ^ 1 > 1 ^ 6
- (2, 5) : 2 ^ 5 > 5 ^ 2

**Input: **A[] = {1, 2, 3}, B[] = {4, 5, 6, 7};**Output:** 7

## Brute Force Approach

The simplest approach is to run two nested loops over the arrays **A[]** and **B[] **and if any of the pairs satisfy the above condition, increment the count.

### C++ Implementation of Brute Force Approach

int countPairs(int A[], int B[], int N, int M) { int count = 0; for (int i = 0; i < N; i++){ for (int j = 0; j < M; j++){ if (pow(A[i], B[j]) > pow(B[j], A[i])){ count++; } } } return ans; }

### Java Implementation of Brute Force Approach

countPairs(int[] A, int[] B, int N, int M) { int count = 0; for (int i = 0; i < N; i++){ for (int j = 0; j < M; j++){ if (Math.pow(A[i], B[j]) > Math.pow(B[j], A[i])){ count++; } } } return ans; }

### Python Implementation of Brute Force Approach

def countPairs(A, B, N, M) { count = 0; for i in range(N): for j in range(M): if (A[i]**B[j] > B[j]**A[i])){ count = count + 1; return ans; }

**Time Complexity:** O(N * M) where N and M are the size of the A[] and B[]**.****Space Complexity:** O(1), as no extra space is used.

## Efficient Approach (Using binary search)

The trick to solving this problem is based on the fact that, for a pair (**X, Y)**, if **Y > X**,

then **X ^ Y > Y ^ X**.

There are a few exceptions, for which this condition fails.

- If
**X = 0**, then**RHS**is always 1 i.e.**0 ^ Y < Y ^ 0**, hence the count for this case is**0**. - If
**X = 1**, then total pairs is equal to the number of**0**’s in the array**B[]**. This is based on the fact that**1 ^ 0 > 0 ^ 1**, but**0 < 1**. - If
**X = 2**. but**Y = 3**or**Y = 4**, the condition fails, as 2 ^ 3 < 3 ^3. Similarly, 2 ^ 4 == 4 ^2

If **X = 3**, but **Y = 2**, we need to consider it since, **3 ^ 2 > 2 ^3** but **2 < 3.**

The exceptions can be shown in tabular format as follows:

**Algorithm**

- Sort the array
**B[]**. - Consider a frequency array to count the frequency of 0, 1, 2, 3, 4 in array
**B[]**. - For every
**ith**element of**A[]**, find the index,**idx**of the smallest element greater than**A[i]**in**B[]**using**binary search**. - To handle the exceptions, follow the below approach:
- If,
**A[i] = 0**, count = 0 - If,
**A[i] = 1**, count = freq[1]**B[]**. - If,
**A[i] = 2**, decrement**count**by frequency of**3**and**4**in**B[]**. - If,
**A[i] = 3**, increment**count**by frequency of**2**in**B[]**.

- If,
- All the integers, after index
**idx**satisfies the above condition, hence count should be incremented by**N – idx**. - Return
**count**.

### C++ Code

int count(int x, int B[], int N, int freq[]) { if (x == 0) return 0; if (x == 1) return freq[0]; int* idx = upper_bound(B, B + M, x); int countx = (B + M) - idx; countx += (freq[0] + freq[1]); if (x == 2) countx -= (freq[3] + freq[4]); if (x == 3) countx += freq[2]; return countx; } int countPairs(int A[], int B[], int N, int M) { int freq[5] = { 0 }; for (int i = 0; i < M; i++) if (B[i] < 5) freq[Y[i]]++; sort(B, B + M); int total_pairs = 0; for (int i = 0; i < N; i++) total_pairs += count(A[i], B, M, freq); return total_pairs; }

### Java Code

count(int x, int B[], int M, int freq[]){ if (x == 0) return 0; if (x == 1) return freq[0]; int idx = Arrays.binarySearch(B, x); int countx = 0; if (idx < 0) { idx = Math.abs(idx + 1); countx = Y.length - idx; } else { while (idx < n && Y[idx] == x) { idx++; } countx = M - idx; } countx += (freq[0] + freq[1]); if (x == 2) countx -= (freq[3] + freq[4]); if (x == 3) countx += freq[2]; return countx; } countPairs(int A[], int B[], int N, int M) { int freq[] = new int[5]; for (int i = 0; i < M; i++) if (B[i] < 5) freq[Y[i]]++; Arrays.sort(B); long total_pairs = 0; for (int i = 0; i < N; i++) total_pairs += count(A[i], B, M, freq); return total_pairs; }

### Python Code

import bisect def count(x, B , n, freq): if x == 0: return 0 if x == 1: return freq[0] idx = bisect.bisect_right(B, x) countx = n - idx ans += freq[0] + freq[1] if x == 2: countx -= freq[3] + freq[4] if x == 3: countx += freq[2] return ans def count_pairs(A, B, N, M): freq = [0] * 5 for i in range(M): if B[i] < 5: freq[B[i]] += 1 B.sort() total_pairs = 0 for x in A: total_pairs += count(x, B, M, freq) return total_pairs

**Time Complexity:** O(N * log N + M * log M), where N and M are the size of the A[] and **B[].Space Complexity:** O(1)

## Practice Questions

Pairs With Given XOR

Pair With Given Difference

## Frequently Asked Questions

**What is the time complexity of the above approach?**The time complexity is

**O(NlogN + MlogM)**, where

**N**and

**M**are the size of arrays

**A[]**and

**B[]**respectively.

**Why do you need to sort the array B[]?**Since we are applying binary search on array

**B,**to count the smallest index greater than

**A[i]**, and binary search works on sorted arrays, we need to sort array

**B[]**.