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
using System ; class GFG { static 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 ; } static int removals ( int [ ] arr , int n , int k ) { int i , j , ans = n - 1 ; Array . Sort ( arr ) ; for ( i = 0 ; i < n ; i ++ ) { j = findInd ( arr [ i ] , i , n , k , arr ) ; if ( j != - 1 ) { ans = Math . Min ( ans , n - ( j - i + 1 ) ) ; } } return ans ; } static void Main ( ) { int [ ] a = { 1 , 3 , 4 , 9 , 10 , 11 , 12 , 17 , 20 } ; int n = a . Length ; int k = 4 ; Console . Write ( removals ( a , n , k ) ) ; } }