#1217

Easy

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Minimum Cost to Move Chips to The Same Position

Compute the minimum cost to move all chips to one position using parity-based greedy moves efficiently.

Problem Statement

You are given an array of integers representing chip positions on a number line. Each chip can be moved either by 2 units with zero cost or 1 unit with cost 1.

Return the minimum total cost required to move all chips to the same position. Optimize using parity-aware reasoning to decide which chips move with cost zero and which incur cost.

Examples

Example 1

Input: position = [1,2,3]

Output: 1

First step: Move the chip at position 3 to position 1 with cost = 0. Second step: Move the chip at position 2 to position 1 with cost = 1. Total cost is 1.

Example 2

Input: position = [2,2,2,3,3]

Output: 2

We can move the two chips at position 3 to position 2. Each move has cost = 1. The total cost = 2.

Example 3

Input: position = [1,1000000000]

Output: 1

Example details omitted.

Constraints

1 <= position.length <= 100
1 <= position[i] <= 10^9

Solution Approach

Count chips by parity

Separate chips into two groups based on even or odd positions. Count how many chips are at even positions and how many at odd positions. This lets you determine which group is cheaper to move.

Apply greedy parity moves

Move all chips in the smaller-count parity group to match the other group. Moves of 2 units are free, so only chips moving across parities contribute to the cost. This greedy choice ensures minimal cost.

Compute and return minimum cost

Compare the counts of even and odd positioned chips. The smaller count directly corresponds to the minimum cost since each chip in that group must be moved across parity with cost 1.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because we iterate once through all chip positions to count parity. Space complexity is O(1) since only two counters are needed regardless of input size.

What Interviewers Usually Probe

Asks if moving by 2 units is free and hints at parity usage.
Mentions small vs large input ranges to test O(n) counting logic.
Checks if candidate can justify why minimum is min(evenCount, oddCount).

Common Pitfalls or Variants

Common pitfalls

Trying to sort the positions unnecessarily, which is not required.
Confusing total moves with total cost by ignoring parity rules.
Applying a dynamic programming approach instead of simple parity counting.

Follow-up variants

What if moves of 2 units also had cost 1?
Consider the problem with positions on a 2D grid maintaining parity.
Generalize to k different types of moves with different costs.

FAQ

How does parity affect the minimum cost in this problem?

Chips on the same parity can be moved among themselves for free, so only chips needing to switch parity incur cost.

Can sorting the positions reduce the cost calculation?

No, sorting is unnecessary; counting chips by parity is sufficient to determine minimal moves.

What is the time complexity of the optimal solution?

O(n), as it only requires a single pass to count even and odd positioned chips.

Why is the greedy choice of moving the smaller parity group optimal?

Because each chip in the smaller group must cross parity, minimizing the number of costly moves ensures minimum total cost.

Does the problem "Minimum Cost to Move Chips to The Same Position" always involve only parity moves?

Yes, the cost rules are based entirely on parity, making parity counting the key to the solution.

terminal

Solution

Solution 1: Quick Thinking

Move all chips at even indices to position 0, and all chips at odd indices to position 1, all at a cost of 0. Then, choose the position (either 0 or 1) with fewer chips and move these chips to the other position. The minimum cost required is the smaller quantity of chips.

1

2

3

4

5

class Solution:
    def minCostToMoveChips(self, position: List[int]) -> int:
        a = sum(p % 2 for p in position)
        b = len(position) - a
        return min(a, b)

Continue Practicing

#1330 reverse subarray to maximize array value #1363 largest multiple of three #976 largest perimeter triangle