Play with Chips: เล่นชิปย้ายตำแหน่งใน C++

ปัญหา

มีชิปอยู่ที่ตำแหน่ง chips[i] สามารถย้ายได้ 2 แบบ:

• ย้าย ±2 หน่วย: Cost = 0
• ย้าย ±1 หน่วย: Cost = 1

หา Cost ต่ำสุด ให้ชิปทุกตัวอยู่ตำแหน่งเดียวกัน

ตัวอย่าง: [2,2,2,3,3] → ย้าย 3,3 ไป 2 (Cost 1+1=2) → 2

ข้อสังเกตสำคัญ

ย้าย ±2 ฟรี → Parity (Odd/Even) ไม่เปลี่ยน ด้วย Cost 0

ย้าย ±1 เปลี่ยน Parity → Cost 1

→ ทุกชิปที่ Parity เดียวกัน รวมกันได้ฟรี

→ เลือก Target Position เป็น Odd หรือ Even ให้ Cost น้อยสุด

Cost = min(จำนวนชิป Odd, จำนวนชิป Even)

โค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minCostToMoveChips(vector<int>& chips) {
        int odd = 0, even = 0;
        for (int pos : chips) {
            if (pos & 1) odd++;
            else even++;
        }
        return min(odd, even);
    }
};

int main() {
    Solution ob;
    vector<int> v = {2, 2, 2, 3, 3};
    cout << ob.minCostToMoveChips(v);  // 2
    return 0;
}

การทำงานตัวอย่าง

Target = Even (2): Odd chips (2 ตัว) ย้าย ±1 → Cost = 2

Target = Odd (3): Even chips (3 ตัว) ย้าย ±1 → Cost = 3

Min = 2

ความซับซ้อน

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

Input / Output

Input:  [2,2,2,3,3]
Output: 2