Skip to content

LeetCode: 1217-Minimum Cost to Move Chips to The Same Position

Last Updated on 2021-12-06 by Clay

題目

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. In one step, we can change the position of the ith chip from position[i] to:

- position[i] + 2 or position[i] - 2 with cost = 0.
- position[i] + 1 or position[i] - 1 with cost = 1.

Return the minimum cost needed to move all the chips to the same position.


題目的意思是,我們有 n 個籌碼,第 i 個籌碼位於 position[i] 的位置。現在,我們要試圖將籌碼全部放在同樣的位置堆疊起來,移動一步的消耗(cost)為 1,移動兩步的消耗為 0。試問:我們要如何在最短的消耗內將全部的籌碼放在同樣的位置?


解題思路

一開始我想的辦法是暴力法是將所有位置移動到 0 或 1...... 但後來轉念一想,其實只需要統計位置是奇數或是偶數就行了。因為我們每次移動兩步的消耗是 0,所以可以把奇數位置籌碼無需消耗地放在 1 的位置、偶數位置籌碼無需消耗地放在 0 位置;接著,就是計算哪邊籌碼比較少,用少的那邊消耗 1 移動一步去另外一邊。

Time complexityO(n)
Space complexityO(1)

C++ 範例程式碼

class Solution {
public:
    int minCostToMoveChips(vector<int>& position) {
        // Init
        int odd = 0;
        int even = 0;

        // Move
        for (int i=0; i<position.size(); ++i) {
            if (position[i] % 2 == 0) {
                ++even;
            }
            else {
                ++odd;
            }
        }
        
        return min(odd, even);
    }
};



Python 範例程式碼

class Solution:
    def minCostToMoveChips(self, position: List[int]) -> int:
        # Init
        odd = 0
        even = 0
        
        # Move
        for n in position:
            if n % 2 == 0: even += 1
            else: odd += 1
        
        return min(odd, even)

References


Read More

Leave a Reply