112. Shave to Zero
A conveyor belt carries crates whose weights are the positive integers in nums, listed in belt order. You must unload crates until exactly x units of weight have been removed. On every step you may take only the crate at the left end or the crate at the right end of the belt that remains.
Return the minimum number of steps needed to remove exactly x units of weight, or -1 if it cannot be done. Removing every crate is allowed when the total weight equals x. Hint: whatever is left after the removals is one contiguous block in the middle of the belt.
Example 1
- Input:
- nums = [3,1,4,2,2], x = 6
- Output:
- 3
- Explanation:
Take 3 and 1 from the left end and one 2 from the right end: three steps removing 3+1+2 = 6.
Example 2
- Input:
- nums = [5,5,5], x = 20
- Output:
- -1
- Explanation:
The total weight is only 15, so 20 can never be reached and the answer is -1.
Example 3
- Input:
- nums = [2,6,1,3], x = 12
- Output:
- 4
- Explanation:
Every crate must go because the total weight is exactly 12, so the answer is 4.
Constraints
1 ≤ nums.length ≤ 105
1 ≤ nums[i] ≤ 104
1 ≤ x ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)