Maximize the minimum difference between any element pair by selecting K elements from given Array | C ++ implementation for the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool isPossibleToSelect ( int arr [ ] , int N , int dif , int K ) { int count = 1 ; int prev = arr [ 0 ] ; for ( int i = 1 ; i < N ; i ++ ) { if ( arr [ i ] >= ( prev + dif ) ) { count ++ ; if ( count == K ) return true ; prev = arr [ i ] ; } } return false ; } int binarySearch ( int arr [ ] , int left , int right , int K , int N ) { int ans = 1 ; while ( left <= right ) { int dif = left + ( right - left ) / 2 ; if ( isPossibleToSelect ( arr , N , dif , K ) ) { ans = max ( ans , dif ) ; left = dif + 1 ; } else right = dif - 1 ; } return ans ; } int main ( ) { int N , K ; N = 7 , K = 4 ; int arr [ ] = { 1 , 4 , 9 , 0 , 2 , 13 , 3 } ; sort ( arr , arr + N ) ; cout << binarySearch ( arr , 0 , arr [ N - 1 ] , K , N ) << " STRNEWLINE " ; return 0 ; }