Last Updated: 13 Apr, 2021
Minimum Number Of Operations To Reach X.
Moderate
Asked in companies
You have been given an array/list ‘ARR’ of integers consisting of ‘N’ integers. You are also given an integer ‘X’. In one operation, you can either remove the leftmost or the rightmost element and add that to the sum of removed elements so far. Your task is to return the minimum number of operations such that the sum of removed elements becomes exactly ‘X’. If it is not possible return -1.
For Example :
Let’s say you have an array/list [1, 3, 5, 3] and ‘X’ is 7.
We can first remove the rightmost element i.e. 3. The array becomes [1,3,5]. In the next step, we can remove the leftmost element i.e 1. The array becomes [3,5] and the sum of removed elements so far becomes 4. In the next step, we can remove the leftmost element i.e 3. The array becomes [5] and the sum of removed elements so far is 7. We have reached our target X i.e 7. Therefore the minimum number of operations to reach ‘X’ is 3.
Input Format :
The first line contains a single integer ‘T’ representing the number of test cases.
The first line of each test case contains two single space-separated integers ‘N’ and ‘X’ representing the size of the array/list ‘ARR’ and the target you need to reach.
The second line and the last line of input contain ‘N’ single space-separated integers representing the array/list elements.
Output Format :
For each test case print the minimum number of operations such that the sum of removed elements becomes exactly ‘X’.If it is not possible print -1.
Print the output of each test case in a separate line.
Note :
You do not need to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 10
1 <= N <= 1000
1 <= X <= 10^9
1 <= ‘ARR[i]’ <= 10^6
Where ‘ARR[i]’ is an element of array/list ARR.
Time Limit: 1sec
Approaches
We have 2 choices at each point either we can take from the left end of the remaining array or the right end of the remaining array. Therefore a total number of ways are ‘2^N’ as we can remove the elements almost ‘N’ times. We just need to run across all possible ways.
Algorithm
- Declare ‘ANS’ and initialize it with ‘-1’.
- Run an iteration from 1 to ‘2^N’
- Declare a variable ‘SUM’ and initialize with zero to store the sum of removed elements.
- Declare a variable ‘OPS’ and initialize with zero to store the number of operations.
- Declare variable ‘LEFT’ and initialize with zero to store the left end of the remaining array.
- Declare variable ‘RIGHT’ and initialize with ‘N-1’ to store the right end of the remaining array.
- Run a loop from ‘1’ to ‘N’ with condition ‘SUM’ is less than ‘X’:-
- If ‘j-th’ bit in ‘i’ is 1 we remove the element from the right end of the array. Add the element to ‘SUM’ and increase ‘OPS’ by 1. Decrease ‘RIGHT’ by 1.
- If ‘j-th’ bit in ‘i’ is 0 we remove the element from the left end of the array. Add the element to ‘SUM’ and increase ‘OPS’ by 1. Increase ‘LEFT’ by 1.
- If ‘SUM’ is exactly ‘X’ and either ‘ANS’ is -1 or ‘OPS’ is less than ‘ANS’, initialize ‘ANS’ with ‘OPS’.
- Return ‘ANS’.
Let’s say if we take first ‘L’ elements from the array and we know minimum elements we need to take from the right end such that ‘SUM’ is greater than equal to ‘X’ is ‘N-R’. As we increase ‘L’, ‘R’ will either remain the same or increase because the sum of elements taken from the left increases. Therefore we can calculate ‘R’ when no elements from ‘L’ are taken. Over the whole iteration pointers ‘L’ and ‘R’ traverse the array just once.
Algorithm
- Declare ‘ANS’ and initialize it with ‘-1’.
- Declare a variable ‘SUM’ and initialize with zero to store the sum of removed elements.
- Initialize ‘R’ with ‘N-1’ and keep on adding elements till we reach the end of the array or ‘SUM’ is not less than ‘X’.
- If ‘SUM’ is exactly ‘X’ initialize ‘ans’ with ‘N-R’.
- Iterate ‘L’ from ‘0’ to ‘N-1’:-
- If ‘R’ == ‘L’ increase ‘R’ by 1, otherwise just add ‘ARR[L]’ to the sum.
- Run a loop till ‘R’ < ‘N’ and ‘SUM’ is greater than ‘X’. If ‘SUM-ARR[R]’ >= ‘X’ then subtract ‘ARR[R]’ from ‘SUM’ and increase ‘R’ by ‘1’. Otherwise, break out of the iteration.
- If ‘SUM’ is exactly ‘X’ and either ‘L+1+N-R’ is less than ‘ANS’ or ‘ANS’ is ‘-1’ then update ‘ANS’ to ‘L+1+N-R’.
- Return ‘ANS’.