Minimum Cost to Move Chips: The Parity Trick

You have n chips, and chip i is at position position[i]. You can move any chip by 2 positions (left or right) at zero cost, or by 1 position at a cost of 1. Your goal is to move all chips to the same position with the minimum total cost. This is LeetCode 1217: Minimum Cost to Move Chips to The Same Position, an easy problem that teaches you to think in terms of parity.

For example, given position = [1, 2, 3], you can move the chip at position 1 to position 3 for free (move by 2), then move the chip at position 2 to position 3 for a cost of 1 (move by 1). The answer is 1.

Why this problem matters

This problem is a clean introduction to parity-based reasoning. Instead of simulating chip movements and comparing all possible target positions, you learn to recognize that "free moves" create equivalence classes. Every even position is equivalent, and every odd position is equivalent. Once you see that, the entire problem collapses into counting two groups and picking the smaller one.

Parity thinking shows up in many contexts beyond this problem. Bitwise operations, graph coloring, and checkerboard arguments all rely on the same idea: splitting elements into two groups based on whether something is odd or even. Getting comfortable with this lens gives you a powerful shortcut for recognizing structure in harder problems.

The key insight

Moving a chip by 2 positions costs nothing. That means you can move a chip from position 1 to position 3 for free. Or from position 3 to position 7 for free. In fact, any sequence of moves-by-2 lets you relocate a chip to any other position that shares the same parity, all for zero cost. A chip at an odd position can reach any other odd position for free. A chip at an even position can reach any other even position for free.

The only time you pay is when a chip crosses from odd to even (or even to odd), which requires at least one move-by-1. That single move costs exactly 1, regardless of which specific odd position or even position the chip starts from.

So the problem reduces to: gather all odd-position chips at one spot for free, gather all even-position chips at one spot for free, then pay 1 per chip to merge the smaller group into the larger group. The answer is simply min(odd_count, even_count).

The solution

def minCostToMoveChips(position):
    odd = sum(1 for p in position if p % 2 != 0)
    even = len(position) - odd
    return min(odd, even)

1. Count how many chips sit at odd positions. A chip at position p is odd when p % 2 != 0.
2. The remaining chips are at even positions: even = len(position) - odd.
3. Return min(odd, even). You always move the smaller group to join the larger one, paying 1 per chip moved.

Visual walkthrough

Every chip ends up at the same position. The only cost came from moving the smaller parity group across the odd/even boundary. No simulation, no brute force, just two counters and a min call.

Complexity analysis

Time: O(n) because you iterate through the position array once, checking parity for each chip.

Space: O(1) because you only store two counters (odd and even), regardless of how many chips there are.

Edge cases

• All chips at the same position [2, 2, 2]: all parities match, so min(0, 3) = 0. No moves needed.
• All odd positions [1, 3, 5]: odd = 3, even = 0. Cost is 0 since all chips share parity.
• All even positions [2, 4, 6]: same logic, cost is 0.
• Single chip [7]: only one chip, already at its position. Cost is 0.
• Two chips, different parity [1, 2]: one odd, one even. Cost is 1.
• Large positions [1, 1000000000]: the actual positions do not matter, only their parity. 1 is odd, 1000000000 is even. Cost is 1.

The building blocks

1. Parity grouping

The pattern of splitting elements into two buckets based on odd/even:

odd = sum(1 for x in values if x % 2 != 0)
even = len(values) - odd

This same decomposition appears in problems about alternating arrays, checkerboard patterns, and graph bipartiteness. The key idea: when some operation is "free" within a parity class, you only pay for transitions between classes.

2. Greedy minimum

Once you have two groups, the greedy choice is always to move the smaller group:

cost = min(group_a, group_b)

This "pick the smaller side" pattern appears in problems like Minimum Moves to Equal Array Elements, where you realize that moving n - 1 elements up by 1 is the same as moving 1 element down by 1. The greedy observation transforms a seemingly complex optimization into a single comparison.

From understanding to recall

You have seen the parity trick and it makes total sense. Two counters, one min call. But will you recognize this pattern the next time a problem hides a free-move parity structure behind a wall of text?

The gap between understanding and recall is where most people lose points in interviews. You read the solution, nod along, and then freeze when you see a variation three weeks later. Spaced repetition closes that gap. You practice identifying the parity grouping pattern, writing the counting loop, and returning the minimum, all from scratch at increasing intervals. After a few rounds, you see "move by 2 is free" and the answer writes itself.

Related posts

• Minimum Moves to Equal Array Elements - Another problem where a greedy parity observation eliminates brute force
• Lemonade Change - Greedy selection with limited resources and a simple priority rule
• Assign Cookies - Greedy matching between two sorted groups

CodeBricks breaks the minimum cost to move chips LeetCode problem into its parity grouping and greedy minimum building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a parity-based question shows up in your interview, you do not think about it. You just write it.