Count pairs ( i , j ) from given array such that i K * arr [ j ] | Java program for the above approach ; 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
class GFG { static int merge ( int arr [ ] , int temp [ ] , int l , int m , int r , int K ) { int i = l ; int j = m + 1 ; int cnt = 0 ; for ( i = l ; i <= m ; i ++ ) { boolean found = false ; while ( j <= r ) { if ( arr [ i ] >= K * arr [ j ] ) { found = true ; } else break ; j ++ ; } if ( found == true ) { cnt += j - ( m + 1 ) ; j -- ; } } int k = l ; i = l ; j = m + 1 ; while ( i <= m && j <= r ) { if ( arr [ i ] <= arr [ j ] ) temp [ k ++ ] = arr [ i ++ ] ; else temp [ k ++ ] = arr [ j ++ ] ; } while ( i <= m ) temp [ k ++ ] = arr [ i ++ ] ; while ( j <= r ) temp [ k ++ ] = arr [ j ++ ] ; for ( i = l ; i <= r ; i ++ ) arr [ i ] = temp [ i ] ; return cnt ; } static int mergeSortUtil ( int arr [ ] , int temp [ ] , int l , int r , int K ) { int cnt = 0 ; if ( l < r ) { int 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 ; } static void mergeSort ( int arr [ ] , int N , int K ) { int temp [ ] = new int [ N ] ; System . out . print ( mergeSortUtil ( arr , temp , 0 , N - 1 , K ) ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 5 , 6 , 2 , 5 } ; int N = arr . length ; int K = 2 ; mergeSort ( arr , N , K ) ; } }