Minimum removals from array to make max | C ++ program for the above approach ; Function to find rightmost index which satisfies the condition arr [ j ] - arr [ i ] <= k ; Initialising start to i + 1 ; Initialising end to n - 1 ; Binary search implementation to find the rightmost element that satisfy the condition ; Check if the condition satisfies ; Store the position ; Make start = mid + 1 ; Make end = mid ; Return the rightmost position ; Function to calculate minimum number of elements to be removed ; Sort the given array ; Iterate from 0 to n - 1 ; Find j such that arr [ j ] - arr [ i ] <= k ; If there exist such j that satisfies the condition ; Number of elements to be removed for this particular case is ( j - i + 1 ) ; Return answer ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findInd ( int key , int i , int n , int k , int arr [ ] ) { int start , end , mid , ind = -1 ; start = i + 1 ; end = n - 1 ; while ( start < end ) { mid = start + ( end - start ) / 2 ; if ( arr [ mid ] - key <= k ) { ind = mid ; start = mid + 1 ; } else { end = mid ; } } return ind ; } int removals ( int arr [ ] , int n , int k ) { int i , j , ans = n - 1 ; sort ( arr , arr + n ) ; for ( i = 0 ; i < n ; i ++ ) { j = findInd ( arr [ i ] , i , n , k , arr ) ; if ( j != -1 ) { ans = min ( ans , n - ( j - i + 1 ) ) ; } } return ans ; } int main ( ) { int a [ ] = { 1 , 3 , 4 , 9 , 10 , 11 , 12 , 17 , 20 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; int k = 4 ; cout << removals ( a , n , k ) ; return 0 ; }