Minimum Removals

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
1 upvote
Asked in company
Amazon

Problem statement

On your 20th birthday, one of your friends gifted you an array 'A' of 'N' positive integers. But you don't like an array having a large difference among numbers. To reduce the difference, you are going to perform the following operations on the array.

Remove an element from the start of the array.
Remove an element from the end of the array.

In one operation, you can remove only one element, either from the start or from the end. Your task is to find the minimum number of operations, after which array 'A' holds the following property -

2 * min > max
Where 'min' is the minimum element of the array, and 'max' is the maximum element of the array, calculated each time for the updated array.

You can perform any operations of your choice, but minimize the number of operations and return it.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer 'T', denoting the number of tests.
 For each Test :
     The first line contains an integer 'N', denoting the length of the array 'A'.
     The second line contains an array 'A' of length 'N'.
Output Format: 
For each test, print an integer, denoting the minimum number of operations required such that the given condition holds true.
Note: 
You are not required to print the expected output. It has already been taken care of. Just implement the function.
Constraints - 
1 <= 'T' <= 5
1 <= 'N' <= 10^5
1 <= A[i] < 10^9  i ∈  (1,N)


Time Limit: 1 sec
Sample Input 1 :
2
4
20 11 4 5
4
5 6 4 7
Sample Output 1 :
2
0
Explanation for Sample Input 1 :
For case 1:
    In two operations, elements [20, 11] are removed. The updated array is [4, 5] for which (2*min > max) holds true, where 'min' = 4 and 'max' = 5.
    One more way to perform operations is removing elements [4, 5]. But the number of operations cannot be less than 2. Hence, the answer is 2.

For Case 2:
    The given array already holds the required condition. Hence no need to perform any operations, and answer becomes 0.
Sample Input 2 :
2
5
4 3 2 1 3
3
2 2 2
Sample Output 2 :
3
0
Hint

Can you check for all possibilities of removals?

Approaches (3)
Brute Force

Approach: Implement a recursive function that accepts the index range to be processed. Initially, the function is called for the entire array, i.e., L= 1 and R = N.

In each recursion call, find the minimum and maximum elements in the array, and if condition (2*min > max) holds, return 0, denoting that 0 removals are needed for range [L, R]. Otherwise, the answer for this call will be [1 + minimum among recursion(L+1, R) and recursion(L, R-1)].


 

Algorithm:

  • Implement a function that takes three parameters: array ‘A’, left endpoint ‘L’, right endpoint ‘R’.
    • Let ‘min’ be the minimum element, and ‘max’ be the maximum element in array ‘A’ for index range [L, R].
    • If (2*min > max) holds true, return 0.
    • Otherwise, return [1 + minimum of recursion(A, L+1, R) and recursion(A, L, R-1) ].
  •  
  • Call the above recursion from the main function for range L=1 and R=N, and return the answer.
Time Complexity

O(N * 2 ^ N), where ‘N’ is the number of elements in the array ‘A’.

Each recursion call is split into two calls, having a total time complexity of O(2 ^ N). In each call, finding minimum and maximum elements costs O(N). Hence overall time complexity becomes O(N * 2 ^ N).

Space Complexity

O(2 ^ N), where ‘N’ is the number of elements in the array ‘A’.

The only space is used by stack for recursion calls. There are 2^N calls in total; hence overall space complexity becomes O(2 ^ N).

Code Solution
(100% EXP penalty)
Minimum Removals
Full screen
Console