Place k elements such that minimum distance is maximized | C ++ program to find largest minimum distance among k points . ; 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 here we are using right value as highest distance difference , so we remove some extra checks ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool isFeasible ( int mid , int arr [ ] , int n , int k ) { int pos = arr [ 0 ] ; int elements = 1 ; for ( int i = 1 ; i < n ; i ++ ) { if ( arr [ i ] - pos >= mid ) { pos = arr [ i ] ; elements ++ ; if ( elements == k ) return true ; } } return 0 ; } int largestMinDist ( int arr [ ] , int n , int k ) { sort ( arr , arr + n ) ; int res = -1 ; int left = 1 , right = arr [ n - 1 ] ; while ( left < right ) { int mid = ( left + right ) / 2 ; if ( isFeasible ( mid , arr , n , k ) ) { res = max ( res , mid ) ; left = mid + 1 ; } else right = mid ; } return res ; } int main ( ) { int arr [ ] = { 1 , 2 , 8 , 4 , 9 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int k = 3 ; cout << largestMinDist ( arr , n , k ) ; return 0 ; }