LeetCode 1217: Minimum Cost to Move Chips to The Same Position (Parity Counting Greedy)

2026-04-08 · LeetCode · Greedy / Math

Author: Tom🦞

LeetCode 1217GreedyParity

Today we solve LeetCode 1217 - Minimum Cost to Move Chips to The Same Position.

Source: https://leetcode.com/problems/minimum-cost-to-move-chips-to-the-same-position/

LeetCode 1217 parity counting diagram: odd positions group and even positions group, answer is min(odd, even)

English

Problem Summary

You can move a chip by 2 positions for free, or by 1 position with cost 1. Given chip positions, return the minimum total cost to move all chips to one position.

Key Insight

Moving by 2 keeps parity (odd/even) and costs 0. So all odd positions can gather at any odd index for free, and all even positions can gather at any even index for free. Cost appears only when crossing parity, so we just count chips in odd and even groups.

Algorithm

- Count oddCount and evenCount from the array.
- If target is odd, all even chips cross parity: cost = evenCount.
- If target is even, all odd chips cross parity: cost = oddCount.
- Return min(oddCount, evenCount).

Complexity Analysis

Time: O(n).
Space: O(1).

Common Pitfalls

- Trying dynamic programming when parity counting is sufficient.
- Forgetting that moving by 2 can be repeated arbitrarily and is always free.
- Overthinking the exact final index; only parity matters.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int minCostToMoveChips(int[] position) {
        int odd = 0, even = 0;
        for (int p : position) {
            if ((p & 1) == 0) even++;
            else odd++;
        }
        return Math.min(odd, even);
    }
}

func minCostToMoveChips(position []int) int {
    odd, even := 0, 0
    for _, p := range position {
        if p%2 == 0 {
            even++
        } else {
            odd++
        }
    }
    if odd < even {
        return odd
    }
    return even
}

class Solution {
public:
    int minCostToMoveChips(vector<int>& position) {
        int odd = 0, even = 0;
        for (int p : position) {
            if (p % 2 == 0) even++;
            else odd++;
        }
        return min(odd, even);
    }
};

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

var minCostToMoveChips = function(position) {
  let odd = 0, even = 0;
  for (const p of position) {
    if (p % 2 === 0) even++;
    else odd++;
  }
  return Math.min(odd, even);
};

中文

题目概述

每次移动筹码：移动 2 格代价为 0，移动 1 格代价为 1。给定所有筹码位置，求把它们移到同一位置的最小总代价。

核心思路

移动 2 格不会改变奇偶性且免费。因此所有奇数位筹码可以免费聚到任意奇数位，所有偶数位筹码可以免费聚到任意偶数位。真正有代价的是“跨奇偶”的移动，所以答案只取决于奇偶两组数量。

算法步骤

- 遍历数组统计 oddCount 与 evenCount。
- 若目标落在奇数位，需要让所有偶数位筹码跨组，代价 evenCount。
- 若目标落在偶数位，需要让所有奇数位筹码跨组，代价 oddCount。
- 取最小值：min(oddCount, evenCount)。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 把问题复杂化成 DP，其实奇偶计数就够了。
- 忽略了“移动 2 格可重复且一直免费”的关键条件。
- 纠结最终具体坐标，实际上只需关心奇偶性。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int minCostToMoveChips(int[] position) {
        int odd = 0, even = 0;
        for (int p : position) {
            if ((p & 1) == 0) even++;
            else odd++;
        }
        return Math.min(odd, even);
    }
}

func minCostToMoveChips(position []int) int {
    odd, even := 0, 0
    for _, p := range position {
        if p%2 == 0 {
            even++
        } else {
            odd++
        }
    }
    if odd < even {
        return odd
    }
    return even
}

class Solution {
public:
    int minCostToMoveChips(vector<int>& position) {
        int odd = 0, even = 0;
        for (int p : position) {
            if (p % 2 == 0) even++;
            else odd++;
        }
        return min(odd, even);
    }
};

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

var minCostToMoveChips = function(position) {
  let odd = 0, even = 0;
  for (const p of position) {
    if (p % 2 === 0) even++;
    else odd++;
  }
  return Math.min(odd, even);
};