human
Count pairs ( i , j ) from given array such that i K * arr [ j ] | Function to merge two sorted arrays.
i : index to left subarray.
j : index to right subarray.
Stores count of pairs that satisfy the given condition.
Traverse to check for the valid conditions.
If condition satisfies.
All elements in the right side of the left subarray also satisfies.
Sort the two given arrays and store in the resultant array.
Elements which are left in the left subarray.
Elements which are left in the right subarray.
Return the count obtained.
Function to partition array into two halves.
Same as ( l + r ) / 2 , but avoids overflow for large l and h.
Sort first and second halves.
Call the merging function.
Function to print the count of required pairs using Merge Sort.
Driver code.
Function Call"
Solution in Python:
assistant
#Here is code to count pairs ( i , j ) from given array such that i K * arr [ j ] and the other steps required.
 def merge ( arr , temp , l , m , r , K ) :
	i = l
	j = m + 1
	cnt = 0
	for l in range ( m + 1 ) :
		found = False
		while ( j <= r ) :
			if ( arr [ i ] >= K * arr [ j ] ) :
				found = True
			else :
				break
			j += 1
		if ( found ) :
			cnt += j - ( m + 1 )
			j -= 1
	k = l
	i = l
	j = m + 1
	while ( i <= m and j <= r ) :
		if ( arr [ i ] <= arr [ j ] ) :
			temp [ k ] = arr [ i ]
			k += 1
			i += 1
		else :
			temp [ k ] = arr [ j ]
			k += 1
			j += 1
	while ( i <= m ) :
		temp [ k ] = arr [ i ]
		k += 1
		i += 1
	while ( j <= r ) :
		temp [ k ] = arr [ j ]
		k += 1
		j += 1
	for i in range ( l , r + 1 ) :
		arr [ i ] = temp [ i ]
	return cnt
def mergeSortUtil ( arr , temp , l , r , K ) :
	cnt = 0
	if ( l < r ) :
		m = ( l + r ) // 2
		cnt += mergeSortUtil ( arr , temp , l , m , K )
		cnt += mergeSortUtil ( arr , temp , m + 1 , r , K )
		cnt += merge ( arr , temp , l , m , r , K )
	return cnt
def mergeSort ( arr , N , K ) :
	temp = [ 0 ] * N
	print ( mergeSortUtil ( arr , temp , 0 , N - 1 , K ) )
arr = [ 5 , 6 , 2 , 5 ]
N = len ( arr )
K = 2
mergeSort ( arr , N , K )