Minimum Cost to Move Chips to the Same Position (LeetCode 1217): It Is All Parity

Chips sit at integer positions. Moving a chip by 2 costs nothing; moving it by 1 costs 1. Find the minimum cost to gather all chips at one position.

The insight

Because moves of 2 are free, any chip can reach any position of the same parity at no cost. So all even chips can gather on one even spot for free, and all odd chips on one odd spot for free. The only cost is moving one whole group across by one step, paying 1 per chip.

So the answer is min(number of even chips, number of odd chips).

def min_cost_to_move_chips(position):
    odd = sum(p % 2 for p in position)
    return min(odd, len(position) - odd)

How to present it

Start with a tiny example, like positions 1, 2 and 3. Show that 1 and 3 merge for free, then one chip pays 1. Interviewers value watching you discover the invariant rather than reciting the formula.

This is a good reminder that many "simulation" problems collapse once you find what stays the same. For live practice on these explanations, the Linkjob AI copilot is what my team works on.

Disclosure: I work on Linkjob AI.