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
< ? php function isFeasible ( $ mid , $ arr , $ n , $ k ) { $ pos = $ arr [ 0 ] ; $ elements = 1 ; for ( $ i = 1 ; $ i < $ n ; $ i ++ ) { if ( $ arr [ $ i ] - $ pos >= $ mid ) { $ pos = $ arr [ $ i ] ; $ elements ++ ; if ( $ elements == $ k ) return true ; } } return 0 ; } function largestMinDist ( $ arr , $ n , $ k ) { sort ( $ arr ) ; $ res = -1 ; $ left = 1 ; $ right = $ arr [ $ n - 1 ] ; while ( $ left < $ right ) { $ mid = ( $ left + $ right ) / 2 ; if ( isFeasible ( $ mid , $ arr , $ n , $ k ) ) { $ res = max ( $ res , $ mid ) ; $ left = $ mid + 1 ; } else $ right = $ mid ; } return $ res ; } $ arr = array ( 1 , 2 , 8 , 4 , 9 ) ; $ n = sizeof ( $ arr ) ; $ k = 3 ; echo largestMinDist ( $ arr , $ n , $ k ) ; ? >