Minimum Number Of Operations To Reach X.

Posted: 13 Apr, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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
Approach 1

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’.
Try Problem