Show problems as
Classic problem #1658MediumArrayHash TableBinary SearchSliding WindowPrefix Sum

Minimum Operations to Reduce X to Zero

Real-world version: Loading Crates From Both Ends
Tracked in this browser only
Read Minimum Operations to Reduce X to Zero on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Crates stand in a single row on a loading dock. Crate i weighs weights[i] kilograms.

A picker can reach only the two ends of the row: one lift takes either the crate at the far left or the crate at the far right and puts it in the van. Once a crate is lifted the row closes up, so its neighbour becomes the new end of the row.

The van has to leave carrying exactly capacity kilograms. Return the smallest number of lifts that gets the loaded weight to exactly capacity, or -1 if no sequence of lifts reaches that weight. A lift count is never negative, so -1 can only mean the load is unreachable.

Examples

Example 1

Input
weights = [3, 2, 20, 1, 4], capacity = 7
Output
2

Lift the 3 kg crate from the left end and the 4 kg crate from the right end. The van carries 3 + 4 = 7 kilograms after two lifts.

Example 2

Input
weights = [1, 1, 1, 9, 5], capacity = 12
Output
4

Lift the three 1 kg crates off the left end, which brings the 9 kg crate to that end, then lift it as well. Four lifts carry 12 kilograms.

Example 3

Input
weights = [2, 4, 6], capacity = 5
Output
-1

No run of lifts off the two ends adds up to 5 kilograms, so the van cannot leave loaded as asked and the answer is -1.

Example 4

Input
weights = [4, 4, 4, 4], capacity = 16
Output
4

Lifting all four crates loads 16 kilograms, which is the requested weight, so four lifts are used.

Constraints

  • 1 <= weights.length <= 10^5
  • 1 <= weights[i] <= 10^4
  • 1 <= capacity <= 10^9

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def fewest_crates(weights: list[int], capacity: int) -> int:
Java
public int fewestCrates(int[] weights, int capacity)

More on the same topics