Show problems as
Classic problem #1674MediumArrayHash TablePrefix Sum

Minimum Moves to Make Array Complementary

Real-world version: Trim the Ballast Tanks
Tracked in this browser only
Read Minimum Moves to Make Array Complementary on LeetCode(opens in a new tab)

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

A survey ship carries an even number of ballast tanks in one line from bow to stern. Write n for the number of tanks. Tank i is mirrored by tank n - 1 - i on the far side of midships. You are given levels, where levels[i] is how many units tank i holds right now, and an integer capacity giving the largest load any tank may hold.

A refill takes one tank and resets it to any load from 1 to capacity inclusive. Each refill counts as one, you may refill the same tank more than once, and a refill is free to leave a tank at the load it already had.

The ship is trimmed when every mirrored pair carries the same combined load, that is, levels[i] + levels[n - 1 - i] is one and the same value for every i.

Return the fewest refills that leave the ship trimmed.

Examples

Example 1

Input
levels = [2, 7, 6, 3, 5, 2], capacity = 9
Output
2

Resetting the fifth tank to 2 and the sixth tank to 7 gives loads [2, 7, 6, 3, 2, 7]. The mirrored pairs are 2 + 7, 7 + 2 and 6 + 3, all totalling 9, which takes 2 refills.

Example 2

Input
levels = [2, 5, 3, 6], capacity = 7
Output
0

The mirrored pairs are 2 + 6 and 5 + 3, both totalling 8, so the ship is already trimmed.

Example 3

Input
levels = [2, 4, 4, 2], capacity = 4
Output
2

Resetting the third tank to 2 and the fourth tank to 4 gives loads [2, 4, 2, 4], whose mirrored pairs are 2 + 4 and 4 + 2, both totalling 6, which takes 2 refills.

Constraints

  • n == levels.length
  • 2 <= n <= 10^5
  • 1 <= levels[i] <= capacity <= 10^5
  • n is even

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_refills(levels: list[int], capacity: int) -> int:
Java
public int minRefills(int[] levels, int capacity)

More on the same topics