Maximum of minimum difference of all pairs from subsequences of given size | C ++ Program to implement the above approach ; Function to check a subsequence can be formed with min difference mid ; If a subsequence of size B with min diff = mid is possible return true else false ; Function to find the maximum of all minimum difference of pairs possible among the subsequence ; Sort the Array ; Stores the boundaries of the search space ; Store the answer ; Binary Search ; If subsequence can be formed with min diff mid and size B ; Right half ; Left half ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool can_place ( int A [ ] , int n , int B , int mid ) { int count = 1 ; int last_position = A [ 0 ] ; for ( int i = 1 ; i < n ; i ++ ) { if ( A [ i ] - last_position >= mid ) { last_position = A [ i ] ; count ++ ; if ( count == B ) { return true ; } } } return false ; } int find_min_difference ( int A [ ] , int n , int B ) { sort ( A , A + n ) ; int s = 0 ; int e = A [ n - 1 ] - A [ 0 ] ; int ans = 0 ; while ( s <= e ) { long long int mid = ( s + e ) / 2 ; if ( can_place ( A , n , B , mid ) ) { ans = mid ; s = mid + 1 ; } else { e = mid - 1 ; } } return ans ; } int main ( ) { int A [ ] = { 1 , 2 , 3 , 5 } ; int n = sizeof ( A ) / sizeof ( A [ 0 ] ) ; int B = 3 ; int min_difference = find_min_difference ( A , n , B ) ; cout << min_difference ; return 0 ; }