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.

#1217

Easy

auto_awesome贪心·invariant

LeetCode 题解工作台

玩筹码

有 n 个筹码。第 i 个筹码的位置是 position[i] 。我们需要把所有筹码移到同一个位置。在一步中，我们可以将第 i 个筹码的位置从 position[i] 改变为: position[i] + 2 或 position[i] - 2 ，此时 cost = 0 position[i] +…

数组数学贪心

题目描述

有 n 个筹码。第 i 个筹码的位置是 position[i] 。

我们需要把所有筹码移到同一个位置。在一步中，我们可以将第 i 个筹码的位置从 position[i] 改变为:

position[i] + 2 或 position[i] - 2 ，此时 cost = 0
position[i] + 1 或 position[i] - 1 ，此时 cost = 1

返回将所有筹码移动到同一位置上所需要的 最小代价 。

示例 1：

输入：position = [1,2,3]
输出：1
解释：第一步:将位置3的筹码移动到位置1，成本为0。
第二步:将位置2的筹码移动到位置1，成本= 1。
总成本是1。

示例 2：

输入：position = [2,2,2,3,3]
输出：2
解释：我们可以把位置3的两个筹码移到位置2。每一步的成本为1。总成本= 2。

示例 3:

输入：position = [1,1000000000]
输出：1

提示：

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

lightbulb

解题思路

方法一：脑筋急转弯

将所有偶数下标的芯片移动到 0 号位置，所有奇数下标的芯片移动到 1 号位置，所有的代价为 0，接下来只需要在 0/1 号位置中选择其中一个较小数量的芯片，移动到另一个位置。所需的最小代价就是那个较小的数量。

时间复杂度 $O(n)$ ，其中 $n$ 为芯片的数量。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

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)

speed

复杂度分析

指标	值
时间	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.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#1330 翻转子数组得到最大的数组值 #1363 形成三的最大倍数 #976 三角形的最大周长