All problems

Minimum Operations to Reduce X to Zero

Medium · sliding window

A row of parcels is given as a list nums, where nums[i] is the weight of the parcel at position i. Every weight is a positive whole number.

You want to collect parcels whose weights add up to exactly x. In one step you may take the parcel at the left end of the row or the parcel at the right end. Once a parcel is taken it is gone, so the next one along becomes the new end.

Return the smallest number of steps needed to collect exactly x in total. If that cannot be done, return -1. Taking every parcel counts as a valid way if all the weights add up to x.

Examples

Example 1

Input: nums = [1, 1, 4, 2, 3], x = 5

Output: 2

Take the 3 from the right end, then the 2 that is now at the right end. That is 5 in two steps.

Example 2

Input: nums = [5, 6, 7, 8, 9], x = 4

Output: -1

Every parcel is heavier than 4, so no way of collecting exactly 4 exists.

Example 3

Input: nums = [3, 2, 20, 1, 1, 3], x = 10

Output: 5

Take 3 and 2 from the left, then 3, 1 and 1 from the right. That is 10 in five steps; the 20 stays in the middle.

Constraints