694. Taking From the Ends to Reach a Total
Remove values one at a time, each from either END of the array, until the removed values add to
exactly x. Print the fewest removals that achieve it, or -1 when it is impossible.
1 1 4 2 3, x = 5 -> 2 take 3 then 2 from the right
5 6 7 8 9, x = 4 -> -1
3 2 20 1 1 3, x = 10 -> 5
## Turn the problem inside out
What is removed is a PREFIX plus a SUFFIX, so what remains is a contiguous MIDDLE. Removing the fewest is the same as leaving the most.
removed = x <=> the middle totals (sum of everything) - x
So: find the LONGEST contiguous stretch whose total is exactly total - x, and the answer is
n minus its length.
Rewriting "take from the two ends" as "leave a middle" is the whole problem. The window machinery then applies unchanged, where it could not have applied to the original wording at all.
## The sweep
All values are positive, so the running sum grows as the window grows and shrinks as it shrinks. That monotonicity is what a window needs.
for hi in 0 .. n-1:
s += a[hi]
while s > target and lo <= hi: s -= a[lo]; lo += 1
if s == target: best = max(best, hi - lo + 1)
## The two cases that are not the sweep
target < 0, meaning x exceeds the whole total: impossible, answer -1.
target == 0, meaning x is exactly the whole total: the middle is empty, which the sweep
never finds because it only considers non-empty windows. The answer is n, and it must be
handled before the loop.
That second case is the one that gets missed, and 1 2 3 with x = 6 is the test.
## Why positivity is required
With a zero or a negative value the running sum is no longer monotone in the window size, the shrink loop can overshoot, and the sweep stops being correct. The constraint says positive for exactly that reason, as it does in problems 689 and 675.
## Overflow
200000 values of up to 10^4 total exactly 2 * 10^9. The move here is to check that
figure against the limit rather than to recognise the shape: a signed 32 bit integer holds
up to 2147483647, so 2000000000 FITS, with about seven percent to spare. This problem
has no overflow, and a 64 bit accumulator buys margin rather than correctness.
The margin is thin enough to be worth the arithmetic. Raise the value cap to 10^5 and the
total becomes 2 * 10^10; raise the length cap to 10^6 and it becomes 10^10. Either
one is an order of magnitude past what 32 bits holds.
## Cost
Time O(n). Space O(1).
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ each value ≤ 10^4` - `1 ≤ x ≤ 10^9`
Input
The first line contains two integers n and x.
The second line contains n positive integers.
Output
Print one integer, the fewest removals, or -1 if the total cannot be reached.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.