Place k elements such that minimum distance is maximized | Returns true if it is possible to arrange k elements of arr [ 0. . n - 1 ] with minimum distance given as mid . ; Place first element at arr [ 0 ] position ; Initialize count of elements placed . ; Try placing k elements with minimum distance mid . ; Place next element if its distance from the previously placed element is greater than current mid ; Return if all elements are placed successfully ; Returns largest minimum distance for k elements in arr [ 0. . n - 1 ] . If elements can 't be placed, returns -1. ; Sort the positions ; Initialize result . ; Consider the maximum possible distance ; Do binary search for largest minimum distance ; If it is possible to place k elements with minimum distance mid , search for higher distance . ; Change value of variable max to mid iff all elements can be successfully placed ; If not possible to place k elements , search for lower distance ; Driver code
def isFeasible ( mid , arr , n , k ) : NEW_LINE INDENT pos = arr [ 0 ] NEW_LINE elements = 1 NEW_LINE for i in range ( 1 , n , 1 ) : NEW_LINE INDENT if ( arr [ i ] - pos >= mid ) : NEW_LINE INDENT pos = arr [ i ] NEW_LINE elements += 1 NEW_LINE if ( elements == k ) : NEW_LINE INDENT return True NEW_LINE DEDENT DEDENT DEDENT return 0 NEW_LINE DEDENT def largestMinDist ( arr , n , k ) : NEW_LINE INDENT arr . sort ( reverse = False ) NEW_LINE res = - 1 NEW_LINE left = 1 NEW_LINE right = arr [ n - 1 ] NEW_LINE while ( left < right ) : NEW_LINE INDENT mid = ( left + right ) / 2 NEW_LINE if ( isFeasible ( mid , arr , n , k ) ) : NEW_LINE INDENT res = max ( res , mid ) NEW_LINE left = mid + 1 NEW_LINE DEDENT else : NEW_LINE INDENT right = mid NEW_LINE DEDENT DEDENT return res NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 2 , 8 , 4 , 9 ] NEW_LINE n = len ( arr ) NEW_LINE k = 3 NEW_LINE print ( largestMinDist ( arr , n , k ) ) NEW_LINE DEDENT