You are given an array of integers of size n where n being even.. You have to calculate the number of dominate pairs (i,j) . Where a pair is called dominant if ( 0<=i<n/2, n/2<=j<n, arr[i]>=5*arr[j] ) these relation are fulfilled.  For example  in arr=[10,3,3,1] index i=0, j=3 form a dominating pair 
Note : 0 based indexing is used  and n is even 
Example 1:
Input:
n=4
arr={10,2,2,1}
Output:
2
Explanation:
As we can see index i=0 and j=2 where
arr[0]>=5*arr[2] (10>=5*2)is fulfilled so
this forms a dominant pair and in same
manner index i=0 and j=3 forms dominant
pair.So total 2 dominant pairs.
Example 2: 
Input:
n=6
arr={10,8,2,1,1,2}
Output:
5
Explanation:
As we can see index i=0 and j=3 where
arr[0]>=5*arr[3] (10>=5*1) is fulfilled so
this forms a dominant pair and in same
manner (0,4),(0,5),(1,3),(1,4) also form
dominant pair.So total 5 dominant pairs.
Your Task:
You don't need to read input or print anything. Your task is to complete the function dominantPairs() which takes an integer n and an array of integers arr respectively and returns the count of dominate pairs.
Expected Time Complexity: O(nlogn)
Expected Auxiliary Space: O(1)
Constraints:
1 <= n<= 10^4
-10^4<=arr[i]<= 10^4
The sum of n over all test cases won't exceed 10^6

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Amortized analysis

Starter code: from typing import List





class Solution:

    def dominantPairs(self, n : int, arr : List[int]) -> int:

        # code here

        



Solutions:
from typing import List

class Solution:

	def dominantPairs(self, n: int, arr: List[int]) -> int:
		arr[:n // 2] = sorted(arr[:n // 2])
		arr[n // 2:] = sorted(arr[n // 2:])
		i = 0
		j = n // 2
		count = 0
		while i < n // 2 and j < n:
			if arr[i] >= 5 * arr[j]:
				count += n // 2 - i
				j += 1
			else:
				i += 1
		return count


from typing import List

class Solution:

	def upper_bound(self, a, num):
		l = 0
		r = len(a) - 1
		ans = -1
		while l <= r:
			mid = (l + r) // 2
			if a[mid] * 5 <= num:
				ans = mid
				l = mid + 1
			else:
				r = mid - 1
		return ans

	def dominantPairs(self, n: int, arr: List[int]) -> int:
		ans = 0
		arr[n // 2:] = sorted(arr[n // 2:])
		arr[:n // 2] = sorted(arr[:n // 2])
		i = 0
		j = n // 2
		while i < n // 2 and j < n:
			while i < n // 2 and arr[i] < arr[j] * 5:
				i += 1
			ans += n // 2 - i
			j += 1
		return ans


from typing import List

class Solution:

	def dominantPairs(self, n: int, arr: List[int]) -> int:
		(c, i, j, x) = (0, 0, 0, 0)
		a = arr[:int(n / 2)]
		b = arr[int(n / 2):]
		for i in range(len(b)):
			b[i] = 5 * b[i]
		a.sort()
		b.sort()
		i = 0
		j = 0
		while i < len(a) and j < len(b):
			if a[i] >= b[j]:
				c = c + 1
				j = j + 1
			else:
				x = x + c * (n / 2 - i)
				i = i + 1
				c = 0
			if j == len(b):
				c = c * (len(b) - i)
				return int(x + c)
		return int(x + c)


from typing import List
from bisect import bisect_right

class Solution:

	def dominantPairs(self, n: int, arr: List[int]) -> int:
		t = sorted(arr[n // 2:])
		result = 0
		for i in range(n // 2):
			ioe = bisect_right(t, arr[i] // 5)
			if arr[i] >= 5 * t[ioe - 1]:
				result += ioe
		return result


from typing import List
from bisect import bisect_right

class Solution:

	def dominantPairs(self, n: int, arr: List[int]) -> int:
		temp = sorted(arr[n // 2:])
		ans = 0
		for i in range(n // 2):
			ind = bisect_right(temp, arr[i] // 5)
			if arr[i] >= 5 * temp[ind - 1]:
				ans += ind
		return ans


from typing import List
import numpy as np

class Solution:

	def dominantPairs(self, n: int, arr: List[int]) -> int:
		arr[0:n // 2] = np.sort(arr[0:n // 2], kind='heapsort')
		arr[n // 2:] = np.sort(arr[n // 2:], kind='heapsort')
		(i, j) = (0, n // 2)
		suma = 0
		while i < n // 2 and j < n:
			if arr[i] >= 5 * arr[j]:
				suma += n // 2 - i
				j += 1
			else:
				i += 1
		return suma


from typing import List

class Solution:

	def dominantPairs(self, n: int, arr: List[int]) -> int:
		c = 0
		i = 0
		j = int(n / 2)
		a1 = arr[0:int(n / 2)]
		a2 = arr[int(n / 2):n]
		a1.sort()
		a2.sort()
		arr = a1 + a2
		while i < int(n / 2) and j < n:
			if arr[i] >= arr[j] * 5:
				c = c + int(n / 2) - i
				j += 1
			else:
				i += 1
		return c


from typing import List

def is_dominant_pair(num_1: int, num_2: int):
	return num_1 >= 5 * num_2

class Solution:

	def dominantPairs(self, n: int, arr: List[int]) -> int:
		bifurcation_index = int(n / 2)
		sum = 0
		component_1 = arr[:bifurcation_index].copy()
		component_1.sort(reverse=True)
		component_2 = arr[bifurcation_index:n].copy()
		component_2.sort(reverse=True)
		i = 0
		j = 0
		while i < bifurcation_index and j < bifurcation_index:
			if is_dominant_pair(component_1[i], component_2[j]):
				sum += bifurcation_index - j
				i += 1
			else:
				j += 1
		return sum


from typing import List

class Solution:

	def dominantPairs(self, n: int, arr: List[int]) -> int:
		l1 = []
		l2 = []
		for i in range(n // 2):
			l1.append(arr[i])
			l2.append(5 * arr[n // 2 + i])
		l1.sort()
		l2.sort()
		(c, i, j) = (0, 0, n // 2)
		while i < n // 2 and j < n:
			if l1[i] >= l2[j - n // 2]:
				c = c + n // 2 - i
				j = j + 1
			else:
				i = i + 1
		return c


from typing import List

class Solution:

	def dominantPairs(self, n: int, arr: List[int]) -> int:
		l1 = arr[:n // 2]
		l2 = arr[n // 2:]
		l1.sort()
		l2.sort()
		l3 = l1 + l2
		i = 0
		j = n // 2
		c = 0
		while i < n / 2 and j < n:
			if l3[i] >= 5 * l3[j]:
				c = c + (len(l1) - i)
				j += 1
			elif l3[i] <= 5 * l3[j]:
				i += 1
		return c


from typing import List

class Solution:

	def get_index_using_binary_search(self, arr, low, high, ele):
		ans = high + 1
		while low <= high:
			mid = (low + high) // 2
			if arr[mid] >= 5 * ele:
				ans = mid
				high = mid - 1
			else:
				low = mid + 1
		return ans

	def dominantPairs(self, n: int, arr: List[int]) -> int:
		arr[:n // 2] = sorted(arr[:n // 2])
		i = 0
		j = n // 2
		ans = 0
		for j in range(n // 2, n):
			i = self.get_index_using_binary_search(arr, 0, n // 2 - 1, arr[j])
			ans += n // 2 - i
		return ans


from typing import List

class Solution:

	def dominantPairs(self, n: int, arr: List[int]) -> int:
		n = len(arr)
		arr_first_half = arr[:n // 2]
		arr_second_half = arr[n // 2:]
		arr_first_half.sort()
		arr_second_half.sort()
		i = 0
		j = 0
		ans = 0
		while i < n // 2 and j < n // 2:
			if arr_first_half[i] >= 5 * arr_second_half[j]:
				ans += n // 2 - i
				j += 1
			else:
				i += 1
		return ans


from typing import List

class Solution:

	def dominantPairs(self, n: int, arr: List[int]) -> int:
		ir = []
		jr = []
		for i in range(n):
			if i < n / 2:
				ir.append(arr[i])
			else:
				jr.append(arr[i])
		ir.sort()
		jr.sort()
		ans = 0
		i = 0
		j = 0
		while j < n / 2 and i < n / 2:
			if ir[i] >= 5 * jr[j]:
				ans = ans + (n / 2 - i)
				j += 1
			else:
				i += 1
		return int(ans)


from typing import List

class Solution:

	def dominantPairs(self, n: int, arr: List[int]) -> int:
		l = [arr[i] for i in range(int(n / 2))]
		r = [arr[i] for i in range(int(n / 2), n)]
		l.sort()
		r.sort()
		ans = 0
		j = 0
		for i in r:
			while j < len(l) and i * 5 > l[j]:
				j += 1
			ans += len(l) - j
		return ans


from typing import List

class Solution:

	def dominantPairs(self, n: int, arr: List[int]) -> int:
		arr[:n // 2] = sorted(arr[:n // 2])
		arr[n // 2:n] = sorted(arr[n // 2:n])
		ans = 0
		j = n // 2
		for i in range(n // 2):
			while j < n and arr[i] >= 5 * arr[j]:
				j += 1
			ans += j - n // 2
		return ans


from typing import List

class Solution:

	def dominantPairs(self, n: int, arr: List[int]) -> int:
		top_half = arr[:n // 2]
		bottom_half = arr[n // 2:]
		top_half.sort()
		bottom_half.sort()
		n_dominant_pairs = 0
		top_ptr = len(top_half) - 1
		bottom_ptr = len(bottom_half) - 1
		while top_ptr >= 0 and bottom_ptr >= 0:
			if top_half[top_ptr] >= 5 * bottom_half[bottom_ptr]:
				n_dominant_pairs += bottom_ptr + 1
				top_ptr -= 1
			else:
				bottom_ptr -= 1
		return n_dominant_pairs


from typing import List

class Solution:

	def dominantPairs(self, n: int, arr: List[int]) -> int:
		m = n // 2
		left = arr[0:m]
		right = arr[m:]
		left.sort()
		right.sort()
		count = 0
		j = 0
		for i in range(0, m):
			while j < m and left[i] >= 5 * right[j]:
				j += 1
			count += j
		return count


from typing import List

class Solution:

	def dominantPairs(self, n: int, arr: List[int]) -> int:
		arr1 = arr[0:n // 2]
		arr2 = arr[n // 2:]
		arr2.sort()
		pairs = 0
		for i in arr1:
			target = i // 5
			pairs += pair(target, arr2)
		return pairs

def pair(target, arr):
	(low, high) = (0, len(arr) - 1)
	while low <= high:
		mid = (low + high) // 2
		if arr[mid] >= target + 1:
			high = mid - 1
		else:
			low = mid + 1
	return low


from typing import List

class Solution:

	def dominantPairs(self, n: int, arr: List[int]) -> int:
		(count, j) = (0, 0)
		(A1, A2) = (arr[:n // 2], arr[n // 2:])
		A1.sort()
		A2.sort()
		for i in A1:
			while j < n // 2 and i >= 5 * A2[j]:
				j += 1
			count += j
		return count


from typing import List
import bisect

class Solution:

	def dominantPairs(self, n: int, arr: List[int]) -> int:
		cnt = 0
		l1 = arr[:n // 2]
		l2 = arr[n // 2:]
		l1.sort()
		l2.sort()
		i = 0
		j = 0
		while i < n // 2 and j < n // 2:
			if l1[i] >= 5 * l2[j]:
				cnt += n // 2 - i
				j += 1
			else:
				i += 1
		return cnt


from typing import List

class Solution:

	def dominantPairs(self, n: int, arr: List[int]) -> int:
		a = arr[:n // 2]
		b = arr[n // 2:]
		a.sort()
		b.sort()
		ar = a + b
		i = 0
		j = n // 2
		c = 0
		while i < n // 2 and j < n:
			if ar[i] < 5 * ar[j]:
				i += 1
			else:
				c = c + n // 2 - i
				j += 1
		return c


from typing import List

class Solution:

	def dominantPairs(self, n: int, arr: List[int]) -> int:
		sum = 0
		a = arr[:n // 2]
		b = arr[n // 2:]
		a.sort()
		b.sort()
		right = 0
		for i in range(n // 2):
			while right < n // 2 and a[i] >= 5 * b[right]:
				right += 1
			sum += right
		return sum


from typing import List

class Solution:

	def dominantPairs(self, n, arr):
		left_part = arr[:n // 2]
		right_part = arr[n // 2:]
		left_part.sort()
		right_part.sort()
		right = 0
		ans = 0
		for left in range(n // 2):
			while right < n // 2 and left_part[left] >= 5 * right_part[right]:
				right += 1
			ans += right
		return ans


from typing import List
from bisect import *

class Solution:

	def dominantPairs(self, n: int, arr: List[int]) -> int:
		lis = sorted(arr[:n // 2])
		ans = 0
		for j in range(n // 2, n):
			ind = bisect_left(lis, 5 * arr[j])
			ans += n // 2 - ind
		return ans


from typing import List

class Solution:

	def dominantPairs(self, n: int, arr: List[int]) -> int:
		lim = n // 2
		for i in range(lim, len(arr)):
			arr[i] *= 5
		srr = sorted([(j, i) for (i, j) in enumerate(arr)], key=lambda x: (x[0], -x[1]))
		res = count = 0
		for (val, ind) in srr:
			if ind >= lim:
				count += 1
			else:
				res += count
		return res


from typing import List
from bisect import *

class Solution:

	def dominantPairs(self, n: int, arr: List[int]) -> int:
		ans = 0
		new = arr[n // 2:]
		new.sort()
		for i in range(n // 2):
			k = bisect_right(new, arr[i] // 5)
			ans += k
		return ans


from typing import List

class Solution:

	def dominantPairs(self, n: int, arr: List[int]) -> int:
		left = arr[:n // 2]
		right = arr[n // 2:]
		left.sort(reverse=True)
		right.sort()
		p1 = 0
		p2 = n // 2 - 1
		ans = 0
		while p1 <= n // 2 and p2 >= 0:
			while p1 < n // 2 and left[p1] >= right[p2] * 5:
				p1 += 1
			ans += p1
			p2 -= 1
		return ans


from typing import List

class Solution:

	def dominantPairs(self, n: int, arr: List[int]) -> int:
		count = 0
		start = 0
		end = 0
		b = []
		a = []
		for i in range(0, n // 2):
			a.append(arr[i])
		for i in range(n // 2, n):
			b.append(arr[i])
		b.sort()
		a.sort()
		while end < len(a) and start < len(b):
			if a[end] >= 5 * b[start]:
				count += len(a) - end
				start += 1
			else:
				end += 1
		return count