Given an array of integers arr[0..n-1], count all pairs (arr[i], arr[j]) in it such that i*arr[i] > j*arr[j],
and 0 ≤ i < j < n.
 
Example 1:
Input :
arr[] = {5, 0, 10, 2, 4, 1, 6}
Output :
5
Explanation :
Pairs which hold condition i*arr[i] > j*arr[j] are
(10, 2) (10, 4) (10, 1) (2, 1) (4, 1)
 
Example 2:
Input :
arr[] = {8, 4, 2, 1}
Output :
2
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function countPairs() which takes the array A[] and its size N as inputs and returns the required result.
 
Expected Time Complexity: O(N. log(N))
Expected Auxiliary Space: O(N. log(N))
 
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ A[ ] ≤ 10^{3}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3

class Solution:    
    def countPairs(self,arr, n): 
         # Your code goes here

Solutions:
def merge(arr, temp, left, mid, right):
	inv_count = 0
	i = left
	j = mid
	k = left
	while i <= mid - 1 and j <= right:
		if arr[i] <= arr[j]:
			temp[k] = arr[i]
			i += 1
			k += 1
		else:
			temp[k] = arr[j]
			k += 1
			j += 1
			inv_count = inv_count + (mid - i)
	while i <= mid - 1:
		temp[k] = arr[i]
		i += 1
		k += 1
	while j <= right:
		temp[k] = arr[j]
		k += 1
		j += 1
	for i in range(left, right + 1):
		arr[i] = temp[i]
	return inv_count

def _mergeSort(arr, temp, left, right):
	inv_count = 0
	if right > left:
		mid = (right + left) // 2
		inv_count = _mergeSort(arr, temp, left, mid)
		inv_count += _mergeSort(arr, temp, mid + 1, right)
		inv_count += merge(arr, temp, left, mid + 1, right)
	return inv_count

class Solution:

	def countPairs(self, arr, n):
		for i in range(n):
			arr[i] = i * arr[i]
		temp = [0] * n
		return _mergeSort(arr, temp, 0, n - 1)


import bisect

class Solution:

	def countPairs(self, arr, n):
		srt_arr = []
		count = 0
		for i in range(n):
			arr[i] = i * arr[i]
			index = bisect.bisect(srt_arr, arr[i])
			count += i - index
			srt_arr.insert(index, arr[i])
		return count


class Solution:

	def countPairs(self, arr, n):
		res = [i * arr[i] for i in range(n)]
		temp = [0] * n
		return self.sorter(res, temp, 0, n - 1)

	def sorter(self, arr, temp, l, r):
		c = 0
		if l < r:
			mid = (l + r) // 2
			c += self.sorter(arr, temp, l, mid)
			c += self.sorter(arr, temp, mid + 1, r)
			c += self.merge(arr, temp, l, mid, r)
		return c

	def merge(self, arr, temp, l, mid, r):
		i = l
		j = mid + 1
		k = l
		c = 0
		while i <= mid and j <= r:
			if arr[i] <= arr[j]:
				temp[k] = arr[i]
				k += 1
				i += 1
			else:
				temp[k] = arr[j]
				c += mid - i + 1
				k += 1
				j += 1
		while i <= mid:
			temp[k] = arr[i]
			k += 1
			i += 1
		while j <= r:
			temp[k] = arr[j]
			k += 1
			j += 1
		arr[l:r + 1] = temp[l:r + 1]
		return c