Maximum of minimum difference of all pairs from subsequences of given size | 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
def can_place ( A , n , B , mid ) : NEW_LINE INDENT count = 1 NEW_LINE last_position = A [ 0 ] NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT if ( A [ i ] - last_position >= mid ) : NEW_LINE INDENT last_position = A [ i ] NEW_LINE count = count + 1 NEW_LINE if ( count == B ) : NEW_LINE INDENT return bool ( True ) NEW_LINE DEDENT DEDENT DEDENT return bool ( False ) NEW_LINE DEDENT def find_min_difference ( A , n , B ) : NEW_LINE INDENT A . sort ( ) NEW_LINE s = 0 NEW_LINE e = A [ n - 1 ] - A [ 0 ] NEW_LINE ans = 0 NEW_LINE while ( s <= e ) : NEW_LINE INDENT mid = ( int ) ( ( s + e ) / 2 ) NEW_LINE if ( can_place ( A , n , B , mid ) ) : NEW_LINE INDENT ans = mid NEW_LINE s = mid + 1 NEW_LINE DEDENT else : NEW_LINE INDENT e = mid - 1 NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT A = [ 1 , 2 , 3 , 5 ] NEW_LINE n = len ( A ) NEW_LINE B = 3 NEW_LINE min_difference = find_min_difference ( A , n , B ) NEW_LINE print ( min_difference ) NEW_LINE