Probability of obtaining pairs from two arrays such that element from the first array is smaller than that of the second array | Function to find probability such that x < y and X belongs to arr1 [ ] & Y belongs to arr2 [ ] ; Stores the length of arr1 ; Stores the length of arr2 ; Stores the result ; Sort the arr2 [ ] in the ascending order ; Traverse the arr1 [ ] ; Stores the count of elements in arr2 that are greater than arr [ i ] ; Increment res by y ; Update the resultant probability ; Return the result ; Function to return the count of elements from the array which are greater than k ; Stores the index of the leftmost element from the array which is at least k ; Finds number of elements greater than k ; If mid element is at least K , then update the value of leftGreater and r ; Update leftGreater ; Update r ; If mid element is at most K , then update the value of l ; Return the count of elements greater than k ; Driver code
def probability ( arr1 , arr2 ) : NEW_LINE INDENT n = len ( arr1 ) NEW_LINE m = len ( arr2 ) NEW_LINE res = 0 NEW_LINE arr2 . sort ( ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT y = countGreater ( arr2 , arr1 [ i ] ) NEW_LINE res += y NEW_LINE DEDENT res /= ( n * m ) NEW_LINE return res NEW_LINE DEDENT def countGreater ( arr , k ) : NEW_LINE INDENT n = len ( arr ) NEW_LINE l = 0 NEW_LINE r = n - 1 NEW_LINE leftGreater = n NEW_LINE while l <= r : NEW_LINE INDENT m = ( l + r ) // 2 NEW_LINE if ( arr [ m ] > k ) : NEW_LINE INDENT leftGreater = m NEW_LINE r = m - 1 NEW_LINE DEDENT else : NEW_LINE INDENT l = m + 1 NEW_LINE DEDENT DEDENT return n - leftGreater NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr1 = [ 5 , 2 , 6 , 1 ] NEW_LINE arr2 = [ 1 , 6 , 10 , 1 ] NEW_LINE print ( probability ( arr1 , arr2 ) ) NEW_LINE DEDENT