Remove numbers from either end of an array so their sum equals x, using as few removals as possible.
You are given an integer array nums and an integer x.
In one operation, you may remove either the leftmost or the rightmost element from nums and subtract its value from x.
Return the minimum number of operations required to make x exactly 0. If it is not possible, return -1.
A useful way to think about the problem is that the elements you do not remove must form one contiguous subarray in the middle of the array. Your goal is to keep the longest such subarray whose sum is sum(nums) - x.
Input Format
- The first line contains an integer
n, the length of the array. - The second line contains
nintegersnums[i]. - The third line contains an integer
x.
Output Format
- Return a single integer: the minimum number of removals from either end needed to reduce
xto0, or-1if impossible.
Constraints
1 <= n <= $10^{5}$1 <= nums[i] <= $10^{4}$1 <= x <= $10^{9}$- The answer should fit in a 32-bit signed integer.
Example 1
Input
nums = [1,1,4,2,3], x = 5
Output
2
Explanation
Remove 2 and 3 from the right, or remove 1 from the left and 4 from the middle is not allowed because removals must be from the ends. The minimum is 2 operations: remove 2 then 3.
Example 2
Input
nums = [5,6,7,8,9], x = 4
Output
-1
Explanation
All numbers are larger than x, and every operation removes an end element, so x can never become exactly 0.
Show 1 more example
Example 3
Input
nums = [3,2,20,1,1,3], x = 10
Output
5
Explanation
Keep the subarray [20] with sum 20 = totalSum - x = 30 - 10. That means removing the other 5 elements from the ends.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.