Minimum removals from array to make max | Function to find rightmost index which satisfies the condition arr [ j ] - arr [ i ] <= k ; Initialising start to i + 1 ; Initialising end to n - 1 ; Binary search implementation to find the rightmost element that satisfy the condition ; Check if the condition satisfies ; Store the position ; Make start = mid + 1 ; Make end = mid ; Return the rightmost position ; Function to calculate minimum number of elements to be removed ; Sort the given array ; Iterate from 0 to n - 1 ; Find j such that arr [ j ] - arr [ i ] <= k ; If there exist such j that satisfies the condition ; Number of elements to be removed for this particular case is ( j - i + 1 ) ; Return answer ; Driver Code
def findInd ( key , i , n , k , arr ) : NEW_LINE INDENT ind = - 1 NEW_LINE start = i + 1 NEW_LINE end = n - 1 ; NEW_LINE while ( start < end ) : NEW_LINE INDENT mid = int ( start + ( end - start ) / 2 ) NEW_LINE if ( arr [ mid ] - key <= k ) : NEW_LINE INDENT ind = mid NEW_LINE start = mid + 1 NEW_LINE DEDENT else : NEW_LINE INDENT end = mid NEW_LINE DEDENT DEDENT return ind NEW_LINE DEDENT def removals ( arr , n , k ) : NEW_LINE INDENT ans = n - 1 NEW_LINE arr . sort ( ) NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT j = findInd ( arr [ i ] , i , n , k , arr ) NEW_LINE if ( j != - 1 ) : NEW_LINE INDENT ans = min ( ans , n - ( j - i + 1 ) ) NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT a = [ 1 , 3 , 4 , 9 , 10 , 11 , 12 , 17 , 20 ] NEW_LINE n = len ( a ) NEW_LINE k = 4 NEW_LINE print ( removals ( a , n , k ) ) NEW_LINE