Show problems as
Classic problem #1217EasyArrayMathGreedy

Minimum Cost to Move Chips to The Same Position

Real-world version: Shunting Pallets Into One Bay
Tracked in this browser only
Read Minimum Cost to Move Chips to The Same Position on LeetCode(opens in a new tab)

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

A loading dock's bays are numbered along a straight line. bays[i] is the bay where pallet i currently sits, and any number of pallets may share a bay.

Pallets are shunted one at a time, and there are two ways to shunt one:

  • send it two bays along, up or down, and pay nothing, because the shuttle rail is geared for a double hop;
  • send it one bay along, up or down, and pay 1.

A pallet may be shunted as many times as you like, and it may pass through or stop in any numbered bay, including bays no pallet started in.

Return the smallest total paid to bring every pallet into one common bay.

Examples

Example 1

Input
bays = [3, 5, 8]
Output
1

Send the pallet in bay 8 down one bay for a charge of 1, then let the shuttle rail carry it down to bay 3 for nothing; the pallet in bay 5 rides the rail to bay 3 free of charge.

Example 2

Input
bays = [4, 4, 4, 7, 7]
Output
2

The two pallets in bay 7 each pay 1 to reach bay 8, and from there the rail takes them to bay 4 alongside the three already sitting in it.

Example 3

Input
bays = [2, 6, 10]
Output
0

All three pallets can ride the shuttle rail all the way to bay 2, so nothing is paid.

Constraints

  • 1 <= bays.length <= 100
  • 1 <= bays[i] <= 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 least_shunt_cost(bays: list[int]) -> int:
Java
public int leastShuntCost(int[] bays)

More on the same topics