Minimum Number Of Operations To Reach X.

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
1 upvote
Asked in companies
OYOAmerican ExpressIntuit

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
4 7
1 2 3 4  
4 4 
1 2 3 4
Sample Output 1 :
2
1
Explanation Of Sample Input 1 :
Test Case 1 :

We can first remove the rightmost element i.e. 4. The array becomes [1,2,3]. In the next step, we can remove the rightmost element i.e 3. The array becomes [1,2]. The sum of removed elements is 7. We have reached our target X i.e 7. Therefore the minimum number of operations is 2.

Therefore the answer is 2.

Test Case 2 :

We can first remove the rightmost element i.e. 4. The array becomes [1,2,3]. The sum of removed elements is 4. We have reached our target X i.e 4. Therefore the minimum number of operations is 1.


Therefore the answer is 1.
Sample Input 2 :
2
4 11
1 2 3 4
8 4
1 2 3 4 4 3 2 1
Sample Output 2 :
-1
3
Hint

Try to think of all possible ways. 

Approaches (2)
Brute Force Approach

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’.
Time Complexity

O(N*2^N), where ‘N’ denotes the size of the array/list.

 

For each of the ‘2^N’ ways, we are iterating the array/list ‘ARR’ of length ‘N’ exactly once. 

Space Complexity

O(1), 

 

We are using constant space.

Code Solution
(100% EXP penalty)
Minimum Number Of Operations To Reach X.
Full screen
Console