Last Updated: 26 Feb, 2021
Minimum Removals
Moderate
Asked in companies
You’re given an array ‘ARR’ of size N and an integer K. Your task is to determine the minimum number of elements that should be removed from the array such that the difference between the maximum and the minimum element in the remaining array is less than or equal to K.
Input Format:
The first line of the input contains an integer T denoting the number of test cases.
The first line of each test case contains two space-separated integers N and K, where N is the size of the array and K is an integer such that the difference between the maximum and minimum element in the remaining array is less than or equal to K.
The second line of each test case contains N space-separated integers, denoting the array elements.
Output Format:
For every test case, print a single line containing a single integer denoting the minimum number of elements that should be removed from the array, such that that the difference between the maximum and minimum element in the remaining array is less than or equal to K.
The output of each test case will be printed in a separate line.
Note :
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= N <= 10 ^ 5
-10 ^ 9 <= ARR[i] <= 10 ^ 9
Time limit: 1 sec
Approaches
We will first sort the given array. Then we will start traversing the array using two variables, say ‘i’ and ‘j,’ using a nested loop, where j will be used to fix the maximum element, and i will be used to fix the minimum element and check if arr[j] - arr[i] <= K.
Algorithm:
- Sort the given array in increasing order.
- Make an integer variable “answer” = N to store the minimum number of elements that need to be removed from the array.
- Run a loop(loop variable ‘i’) from 0 till N - 1 to fix the minimum element in the array.
- Run a nested loop(loop variable ‘j’) from i till N -1 to fix the maximum element in the array.
- If arr[j] - arr[i] <= K, then update answer = min(answer, N - (j - i + 1) ), because we will be removing all the elements from the array except those elements which are present at index i to j.
- Return answer.
We will first sort the given array. Now, observe that what is the maximum number from which the first element(arr[0]) can be subtracted such that their difference is less than or equal to K. This number is arr[0] + K. Now, we’ll search for this number in the array or the number which is smaller than this number in the given array using binary search.
Algorithm:
- Sort the given array in increasing order.
- Make an integer variable “answer,” initialize it to N -1 because the maximum elements that can be removed are N -1.
- Run a loop(loop variable ‘i’) from 0 till N -1.
- Make an integer “pos,” which will give the index of the element that is equal to arr[i] + K, or the element just smaller than arr[i] + K in the given array.
- Find the “pos” using binary search.
- Update answer = min(n -1 - (pos-i), answer) because we are only keeping the array region that starts from ‘i’ and ends at “pos” and deleting the remaining array elements.
- Return answer.
Similar problems