Show problems as
Classic problem #2366HardArrayMathGreedy

Minimum Replacements to Sort the Array

Real-world version: Cutting Crates Into a Rising Manifest
Tracked in this browser only
Read Minimum Replacements to Sort the Array on LeetCode(opens in a new tab)

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

A freight manifest lists crate weights in loading order as weights. The loader will only accept the manifest when the weights never decrease as you read it from the first entry to the last.

One cut takes a single crate of weight w and replaces it with two crates whose weights are positive whole numbers adding up to w. The two new crates take the cut crate's place in the manifest, one after the other, so the manifest gets one entry longer. Either of the new crates may be cut again later.

Return the least number of cuts that makes the manifest never decrease.

Examples

Example 1

Input
weights = [12, 8, 6]
Output
3

Cut the 8 into 4 and 4, then cut the 12 into 4 and 8 and cut that 8 into 4 and 4. The manifest now reads 4, 4, 4, 4, 4, 6, which never decreases, after three cuts.

Example 2

Input
weights = [10, 3, 3]
Output
3

Three cuts turn the 10 into 2, 2, 3 and 3, leaving the manifest reading 2, 2, 3, 3, 3, 3, which never decreases.

Example 3

Input
weights = [2, 4, 6]
Output
0

The manifest already never decreases, so no cut is needed.

Constraints

  • 1 <= weights.length <= 10^5
  • 1 <= weights[i] <= 10^9
  • The answer is at most 10^15 for every input allowed above.

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 min_crate_splits(weights: list[int]) -> int:
Java
public long minCrateSplits(int[] weights)

More on the same topics