Maximize the minimum difference between any element pair by selecting K elements from given Array | To check if selection of K elements is possible such that difference between them is greater than dif ; Selecting first element in the sorted array ; prev is the previously selected element initially at index 0 as first element is already selected ; Check if selection of K - 1 elements from array with a minimum difference of dif is possible ; If the current element is atleast dif difference apart from the previously selected element then select the current element and increase the count ; If selection of K elements with a min difference of dif is possible then return true ; Prev will become current element for the next iteration ; If selection of K elements with minimum difference of dif is not possible then return false ; Minimum largest difference possible is 1 ; Check if selection of K elements is possible with a minimum difference of dif ; If dif is greater than previous ans we update ans ; Continue to search for better answer . Try finding greater dif ; K elements cannot be selected ; Driver code ; arr should be in a sorted order
def isPossibleToSelect ( arr , N , dif , K ) : NEW_LINE INDENT count = 1 NEW_LINE prev = arr [ 0 ] NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT if ( arr [ i ] >= ( prev + dif ) ) : NEW_LINE INDENT count += 1 NEW_LINE if ( count == K ) : NEW_LINE INDENT return True NEW_LINE DEDENT prev = arr [ i ] NEW_LINE DEDENT DEDENT return False NEW_LINE DEDENT def binarySearch ( arr , left , right , K , N ) : NEW_LINE INDENT ans = 1 NEW_LINE while ( left <= right ) : NEW_LINE INDENT dif = left + ( right - left ) // 2 NEW_LINE if ( isPossibleToSelect ( arr , N , dif , K ) ) : NEW_LINE INDENT ans = max ( ans , dif ) NEW_LINE left = dif + 1 NEW_LINE DEDENT else : NEW_LINE INDENT right = dif - 1 NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 7 NEW_LINE K = 4 NEW_LINE arr = [ 1 , 4 , 9 , 0 , 2 , 13 , 3 ] NEW_LINE arr . sort ( ) NEW_LINE print ( binarySearch ( arr , 0 , arr [ N - 1 ] , K , N ) ) NEW_LINE DEDENT