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
def merge ( arr , temp , l , m , r , K ) : NEW_LINE INDENT i = l NEW_LINE j = m + 1 NEW_LINE cnt = 0 NEW_LINE for l in range ( m + 1 ) : NEW_LINE INDENT found = False NEW_LINE while ( j <= r ) : NEW_LINE INDENT if ( arr [ i ] >= K * arr [ j ] ) : NEW_LINE INDENT found = True NEW_LINE DEDENT else : NEW_LINE INDENT break NEW_LINE DEDENT j += 1 NEW_LINE DEDENT if ( found ) : NEW_LINE INDENT cnt += j - ( m + 1 ) NEW_LINE j -= 1 NEW_LINE DEDENT DEDENT k = l NEW_LINE i = l NEW_LINE j = m + 1 NEW_LINE while ( i <= m and j <= r ) : NEW_LINE INDENT if ( arr [ i ] <= arr [ j ] ) : NEW_LINE INDENT temp [ k ] = arr [ i ] NEW_LINE k += 1 NEW_LINE i += 1 NEW_LINE DEDENT else : NEW_LINE INDENT temp [ k ] = arr [ j ] NEW_LINE k += 1 NEW_LINE j += 1 NEW_LINE DEDENT DEDENT while ( i <= m ) : NEW_LINE INDENT temp [ k ] = arr [ i ] NEW_LINE k += 1 NEW_LINE i += 1 NEW_LINE DEDENT while ( j <= r ) : NEW_LINE INDENT temp [ k ] = arr [ j ] NEW_LINE k += 1 NEW_LINE j += 1 NEW_LINE DEDENT for i in range ( l , r + 1 ) : NEW_LINE INDENT arr [ i ] = temp [ i ] NEW_LINE DEDENT return cnt NEW_LINE DEDENT def mergeSortUtil ( arr , temp , l , r , K ) : NEW_LINE INDENT cnt = 0 NEW_LINE if ( l < r ) : NEW_LINE INDENT m = ( l + r ) // 2 NEW_LINE cnt += mergeSortUtil ( arr , temp , l , m , K ) NEW_LINE cnt += mergeSortUtil ( arr , temp , m + 1 , r , K ) NEW_LINE cnt += merge ( arr , temp , l , m , r , K ) NEW_LINE DEDENT return cnt NEW_LINE DEDENT def mergeSort ( arr , N , K ) : NEW_LINE INDENT temp = [ 0 ] * N NEW_LINE print ( mergeSortUtil ( arr , temp , 0 , N - 1 , K ) ) NEW_LINE DEDENT arr = [ 5 , 6 , 2 , 5 ] NEW_LINE N = len ( arr ) NEW_LINE K = 2 NEW_LINE mergeSort ( arr , N , K ) NEW_LINE