Flip to Zeros in C++: หาจำนวน Operation น้อยที่สุดเพื่อทำให้ Array เป็น 0 ทั้งหมด

กำหนด array nums ที่มีแค่ 0 และ 1 Operation หนึ่งครั้งคือเลือก index i แล้ว flip (0↔1) ทุกตัวตั้งแต่ i ถึงปลาย array หาจำนวน operation น้อยที่สุดเพื่อทำให้ทุกตัวเป็น 0

ตัวอย่าง: [1,0,1] → Output: 3

ขั้นตอน: flip index 0 → [0,1,0], flip index 1 → [0,0,1], flip index 2 → [0,0,0]

วิธีแก้ปัญหา (Prefix Flip Tracking)

ใช้ array op ติดตามจำนวนครั้งที่ flip ผ่านแต่ละ index
วน i จาก 0 ถึง n-1:
- op[i] += op[i-1] (สะสม flip จากด้านซ้าย)
- ถ้า (nums[i] + op[i]) % 2 == 1 (ค่าปัจจุบันเป็น 1) ให้ flip ที่ i: op[i]++, ret++

ตัวอย่างโค้ด C++

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

class Solution {
public:
    int solve(vector<int>& nums) {
        int n = nums.size();
        vector<int> op(n);
        int ret = 0;
        for(int i = 0; i < n; i++) {
            if(i > 0) op[i] += op[i-1];
            if((nums[i] + op[i]) & 1) {
                op[i]++;
                ret++;
            }
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,0,1};
    cout << ob.solve(v);
}

Input

{1,0,1}