Minimum Cost to Move Chips to The Same Position — LeetCode 1217 Python Solution

The problem

We have n chips, where the position of the ith chip is position[i]. We need to move all the chips to the same position.

Example

Input

position = [1,2,3]

Output

1

Explanation

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

Python solution

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)

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 1217. Minimum Cost to Move Chips to The Same Position is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems