Given two arrays X[] and Y[] of size M and N respectively. Find number of pairs such that x^{y} > y^{x} where x is an element from X[] and y is an element from Y[].
Example 1:
Input:
M = 3, N = 2
X[] = {2, 1, 6}, Y = {1, 5}
Output: 3
Explanation: There are total 3 pairs 
where pow(x, y) is greater than pow(y, x) 
Pairs are (2, 1), (2, 5) and (6, 1).
Example 2:
Input:
M = 3, N = 3
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).
Your Task:
You don't need to read input or print anything. Your task is to complete the function countPairs() which takes array X[], array Y[], m and n as input parameters and returns an integer denoting the number of pairs that are true to the given condition. 
Expected Time Complexity: O(N*logN + M*logM)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ M, N ≤ 10^{5}
1 ≤ X[i], Y[i] ≤ 10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Data structures

Starter code: #User function Template for python3

class Solution:
    def countPairs(self,X, Y, m, n):
        # code here

Solutions:
class Solution:

	def countPairs(self, X, Y, m, n):
		for i in range(m):
			X[i] **= 1 / X[i]
		for i in range(n):
			Y[i] **= 1 / Y[i]
		X.sort()
		Y.sort()
		i = j = 0
		ans = 0
		while i < m:
			if j == n:
				ans += n
			else:
				while j < n and X[i] > Y[j]:
					j += 1
				ans += j
			i += 1
		return ans


import bisect

class Solution:

	def countPairs(self, X, Y, m, n):
		X.sort()
		Y.sort()
		ans = 0
		for x in X:
			if x == 1:
				continue
			elif x == 2:
				idx = bisect.bisect_left(Y, 5)
				ans += n - idx
			elif x == 3:
				idx = bisect.bisect_left(Y, 2)
				ans += n - idx
				ans -= bisect.bisect(Y, 3) - bisect.bisect_left(Y, 3)
			else:
				idx = bisect.bisect_left(Y, x + 1)
				ans += n - idx
		for y in Y:
			if y == 1:
				idx = bisect.bisect_left(X, 2)
				ans += m - idx
		return ans


class Solution:

	def countPairs(self, X, Y, m, n):
		import math
		(x, y) = ([0] * m, [0] * n)
		for i in range(m):
			if X[i] == 1:
				x[i] = float('inf')
			else:
				temp = X[i] * 1.0
				temp = temp / math.log(temp)
				x[i] = temp
		for i in range(n):
			if Y[i] == 1:
				y[i] = float('inf')
			else:
				temp = Y[i] * 1.0
				temp = temp / math.log(temp)
				y[i] = temp
		x.sort()
		y.sort()
		i = j = count = 0
		while i < m and j < n:
			if x[i] < y[j]:
				count += n - j
				i += 1
			else:
				j += 1
		return count


import bisect as bs

class Solution:

	def countPairs(self, X, Y, m, n):
		(y1, y0, y2, y3, y4) = (0, 0, 0, 0, 0)
		X.sort()
		Y.sort()
		count = 0
		for i in range(n):
			if Y[i] == 0:
				y0 += 1
			elif Y[i] == 1:
				y1 += 1
			elif Y[i] == 2:
				y2 += 1
			elif Y[i] == 3:
				y3 += 1
			elif Y[i] == 4:
				y4 += 1
		for i in range(m):
			if X[i] == 0:
				continue
			elif X[i] == 1:
				count += y0
			elif X[i] == 2:
				k = bs.bisect_right(Y, 2)
				count += n - k
				count -= y3
				count -= y4
				count += y1 + y0
			else:
				j = bs.bisect_right(Y, X[i])
				count += n - j
				count += y1 + y0
				if X[i] == 3:
					count += y2
		return count


from bisect import *

class Solution:

	def countPairs(self, X, Y, m, n):
		one = 0
		two = 0
		for ele in Y:
			if ele == 1:
				one += 1
			if ele == 2:
				two += 1
		X.sort()
		Y.sort()
		ans = 0
		for x in X:
			if x == 1:
				continue
			else:
				ans += one
				if x == 2:
					ans += n - bisect_left(Y, 5)
					continue
				elif x == 3:
					ans += two
				ans += n - bisect_left(Y, x + 1)
		return ans


from bisect import *

class Solution:

	def countPairs(self, X, Y, m, n):
		y2 = 0
		y3 = 0
		y1 = 0
		for ele in Y:
			if ele != 2 and ele != 3 and (ele != 4):
				y2 += 1
			if ele != 3:
				y3 += 1
			if ele == 1:
				y1 += 1
		X.sort()
		Y.sort()
		ans = 0
		for x in X:
			if x == 1:
				continue
			elif x == 2:
				ans += y2
			elif x == 3:
				ans += y3
			else:
				ans += y1
				ans += n - bisect_left(Y, x + 1)
		return ans


from collections import Counter

class Solution:

	def countPairs(self, X, Y, m, n):
		XC = sorted(Counter(X).items())
		YC = Counter(Y)
		Y = sorted(YC.items())
		(ans, i, left) = (0, 0, n - (YC[2] + YC[3] + YC[4]))
		if XC[i][0] == 1:
			i += 1
		if XC[i][0] == 2:
			ans += XC[i][1] * left
			i += 1
		if XC[i][0] == 3:
			ans += XC[i][1] * (n - YC[3])
			i += 1
		if XC[i][0] == 4:
			ans += XC[i][1] * left
			i += 1
		(j, yleft) = (0, n)
		while i < len(XC):
			(v, xcnt) = XC[i]
			ans += YC[1] * xcnt
			while j < len(Y) and Y[j][0] <= v:
				yleft -= Y[j][1]
				j += 1
			ans += yleft * xcnt
			i += 1
		return ans


class Solution:

	def get_index(self, y, n, ele):
		ans = -1
		low = 0
		high = n - 1
		while low <= high:
			mid = (low + high) // 2
			if Y[mid] > ele:
				ans = mid
				high = mid - 1
			else:
				low = mid + 1
		return ans

	def countPairs(self, X, Y, m, n):
		X.sort()
		Y.sort()
		y_c0 = Y.count(0)
		y_c1 = Y.count(1)
		y_c3 = Y.count(3)
		y_c4 = Y.count(4)
		y_c2 = Y.count(2)
		i = 0
		j = 0
		ind = -1
		c = 0
		for i in range(m):
			if X[i] == 0:
				continue
			elif X[i] == 1:
				c += y_c0
			elif X[i] == 2:
				ind = self.get_index(Y, n, 2)
				if ind != -1:
					c += n - ind
				c -= y_c3
				c -= y_c4
				c += y_c1 + y_c0
			else:
				ind = self.get_index(Y, n, X[i])
				if ind != -1:
					c += n - ind
				c += y_c1 + y_c0
				if X[i] == 3:
					c += y_c2
		return c


import bisect

class Solution:

	def count(self, x, Y, n, NoOfY):
		if x == 0:
			return 0
		if x == 1:
			return NoOfY[0]
		idx = bisect.bisect_right(Y, x)
		ans = n - idx
		ans += NoOfY[0] + NoOfY[1]
		if x == 2:
			ans -= NoOfY[3] + NoOfY[4]
		if x == 3:
			ans += NoOfY[2]
		return ans

	def countPairs(self, X, Y, m, n):
		NoOfY = [0] * 5
		for i in range(n):
			if Y[i] < 5:
				NoOfY[Y[i]] += 1
		Y.sort()
		total_pairs = 0
		for x in X:
			total_pairs += self.count(x, Y, n, NoOfY)
		return total_pairs


class Solution:

	def bina(self, x, g, n):
		l = 0
		h = n - 1
		ans = -1
		while l <= h:
			m = (l + h) // 2
			if g[m] > x:
				ans = m
				h = m - 1
			else:
				l = m + 1
		return ans

	def countPairs(self, a, b, M, N):
		s = {}
		for i in range(5):
			s[i] = 0
		for i in b:
			if i in s:
				s[i] += 1
		b.sort()
		a.sort()
		c = 0
		for i in a:
			if i == 0:
				continue
			elif i == 1:
				c += s[0]
			elif i == 2:
				ind = self.bina(i, b, N)
				if ind != -1:
					c += N - ind
				c += s[1] + s[0] - s[3] - s[4]
			else:
				ind = self.bina(i, b, N)
				if ind != -1:
					c += N - ind
				c += s[0] + s[1]
				if i == 3:
					c += s[2]
		return c


import bisect

class Solution:

	def count(self, x, Y, n, freq):
		if x == 1:
			return freq[0]
		idx = bisect.bisect_right(Y, x)
		ans = n - idx
		ans += freq[0] + freq[1]
		if x == 2:
			ans -= freq[3] + freq[4]
		if x == 3:
			ans += freq[2]
		return ans

	def countPairs(self, X, Y, m, n):
		freq = [0] * 5
		Y.sort()
		for i in Y:
			if i < 5:
				freq[i] += 1
		count_ans = 0
		for i in X:
			count_ans += self.count(i, Y, n, freq)
		return count_ans


from bisect import bisect_right

class Solution:

	def countPairs(self, X, Y, m, n):
		NoY = [0] * 5
		for i in Y:
			if i < 5:
				NoY[i] += 1
		Y.sort()
		ans = 0
		for i in X:
			ans += self.count(i, Y, n, NoY)
		return ans

	def count(self, x, y, n, a):
		if x == 0:
			return 0
		if x == 1:
			return a[0]
		i = bisect_right(y, x)
		ans = n - i
		ans += a[0] + a[1]
		if x == 2:
			ans -= a[3] + a[4]
		if x == 3:
			ans += a[2]
		return ans
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		(m, n) = list(map(int, input().strip().split()))
		X = list(map(int, input().strip().split()))
		Y = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.countPairs(X, Y, m, n)
		print(ans)
		tc -= 1


import bisect

class Solution:

	def countPairs(self, X, Y, m, n):
		Y.sort()
		noOfYs = [0 for _ in range(5)]
		for i in range(n):
			if Y[i] < 5:
				noOfYs[Y[i]] += 1
		pairs = 0
		for x in X:
			pairs += self.count(x, Y, noOfYs, n)
		return pairs

	def count(self, x, Y, noOfYs, n):
		if x == 0:
			return 0
		if x == 1:
			return noOfYs[0]
		idx = bisect.bisect_right(Y, x)
		res = n - idx
		res += noOfYs[1] + noOfYs[0]
		if x == 2:
			res -= noOfYs[3] + noOfYs[4]
		if x == 3:
			res += noOfYs[2]
		return res


import bisect

class Solution:

	def countPairs(self, X, Y, m, n):
		NoOfYs = [0 for _ in range(5)]
		for i in range(n):
			if Y[i] < 5:
				NoOfYs[Y[i]] += 1
		Y.sort()
		pairs = 0
		for x in X:
			pairs += self.count(x, Y, NoOfYs)
		return pairs

	def count(self, x, Y, noOfYs):
		if x == 0:
			return 0
		if x == 1:
			return noOfYs[0]
		idx = bisect.bisect_right(Y, x)
		res = len(Y) - idx
		res += noOfYs[0] + noOfYs[1]
		if x == 2:
			res -= noOfYs[3] + noOfYs[4]
		if x == 3:
			res += noOfYs[2]
		return res

	def binarySearch(self, Y, x):
		low = 0
		high = len(Y) - 1
		idx = -1
		while low <= high:
			mid = (low + high) // 2
			if Y[mid] > x:
				idx = mid
				high = mid - 1
			else:
				low = mid + 1
		return idx


import math
import sys

class Solution:

	def countPairs(self, X, Y, m, n):
		arr1 = X
		arr2 = Y
		for i in range(len(arr1)):
			if arr1[i] == 1:
				arr1[i] = sys.maxsize
			else:
				arr1[i] = arr1[i] / math.log(arr1[i])
		arr1.sort()
		for j in range(len(arr2)):
			if arr2[j] == 1:
				arr2[j] = sys.maxsize
			else:
				arr2[j] = arr2[j] / math.log(arr2[j])
		arr2.sort()
		pointA = 0
		pointB = 0
		count = 0
		while pointA < len(arr1) and pointB < len(arr2):
			if arr1[pointA] < arr2[pointB]:
				count += len(arr2) - pointB
				pointA += 1
			else:
				pointB += 1
		return count


import bisect

class Solution:

	def count(self, i, Y, m, res):
		if i == 0:
			return 0
		if i == 1:
			return res[0]
		ind = bisect.bisect_right(Y, i)
		ans = m - ind
		ans += res[0] + res[1]
		if i == 2:
			ans -= res[3] + res[4]
		if i == 3:
			ans += res[2]
		return ans

	def countPairs(self, X, Y, m, n):
		cnt = 0
		result = [0] * 5
		for i in range(n):
			if Y[i] < 5:
				result[Y[i]] += 1
		Y.sort()
		for i in X:
			cnt += self.count(i, Y, n, result)
		return cnt


def search(arr, l, r, x):
	if r >= l:
		mid = l + (r - l) // 2
		if arr[mid] <= x:
			return search(arr, mid + 1, r, x)
		else:
			return search(arr, l, mid - 1, x)
	return l

class Solution:

	def countPairs(self, X, Y, m, n):
		nn = [0] * 5
		for i in range(n):
			if Y[i] < 5:
				nn[Y[i]] += 1
		Y.sort()
		pairs = 0
		for i in X:
			if i == 0:
				continue
			elif i == 1:
				pairs += nn[0]
			else:
				ss = search(Y, 0, n - 1, i)
				if ss > n - 1:
					ss = 0
				else:
					pairs += n - ss
				pairs += nn[0] + nn[1]
				if i == 2:
					pairs -= nn[3] + nn[4]
				if i == 3:
					pairs += nn[2]
		return pairs


import bisect

class Solution:

	def bs(self, arr, low, high, x):
		if low <= high:
			mid = low + (high - low) // 2
			if (mid == 0 or arr[mid - 1] <= x) and arr[mid] > x:
				return mid
			elif arr[mid] <= x:
				return self.bs(arr, mid + 1, high, x)
			else:
				return self.bs(arr, low, mid - 1, x)
		else:
			return -1

	def count(self, x, Y, n, NoOfY):
		if x == 0:
			return 0
		if x == 1:
			return NoOfY[0]
		idx = bisect.bisect_right(Y, x)
		ans = n - idx
		ans += NoOfY[0] + NoOfY[1]
		if x == 2:
			ans -= NoOfY[3] + NoOfY[4]
		if x == 3:
			ans += NoOfY[2]
		return ans

	def countPairs(self, X, Y, m, n):
		NoOfY = [0] * 5
		for i in range(n):
			if Y[i] < 5:
				NoOfY[Y[i]] += 1
		Y.sort()
		total_pairs = 0
		for x in X:
			total_pairs += self.count(x, Y, n, NoOfY)
		return total_pairs


import bisect

class Solution:

	def count(self, i, b, n, hashe):
		if i == 0:
			return 0
		if i == 1:
			return hashe[0]
		index = bisect.bisect_right(b, i)
		ans = n - index
		ans += hashe[1] + hashe[0]
		if i == 2:
			ans -= hashe[3]
			ans -= hashe[4]
		if i == 3:
			ans += hashe[2]
		return ans

	def countPairs(self, a, b, M, N):
		pairs = 0
		hashe = dict()
		hashe = [0 for i in range(5)]
		for i in b:
			if i < 5:
				hashe[i] += 1
		b.sort()
		for i in a:
			pairs += self.count(i, b, N, hashe)
		return pairs