จำนวนการพลิกบิต K ติดกันน้อยที่สุดใน C++

คำอธิบายปัญหา

ให้อาร์เรย์ A ประกอบด้วย 0 และ 1 การ K-bit flip คือเลือกซับอาร์เรย์ติดต่อกันยาว K แล้วพลิกบิตทั้งหมด (0↔1) หาจำนวนการพลิกน้อยที่สุดเพื่อให้ไม่มี 0 เหลือ หากไม่ได้คืน -1

ตัวอย่าง

A = [0,0,0,1,0,1,1,0], K = 3 → Output: 3
1) flip [0..2] → [1,1,1,1,0,1,1,0]
2) flip [4..6] → [1,1,1,1,1,0,0,0]
3) flip [5..7] → [1,1,1,1,1,1,1,1]

แนวทางแก้ปัญหา: Difference Array / Sweep Line

ใช้อาร์เรย์ moves[i] เก็บจำนวนครั้งที่เริ่มการพลิกที่ตำแหน่ง i ใช้ prefix sum ของ moves เพื่อรู้ว่าตำแหน่ง i ถูกพลิกกี่ครั้ง

อัลกอริทึม

1. curr = 0 (prefix sum ของ moves)
2. วน i = 0 ถึง n-K:
   • curr += moves[i]
   • ค่าจริงที่ i = (A[i] + curr) % 2
   • ถ้าเป็น 0 → ต้องพลิก: moves[i]++, moves[i+K]--, counter++
3. ตรวจสอบตำแหน่งที่เหลือ (i = n-K+1 .. n-1) ว่าทั้งหมดเป็น 1 แล้วหรือไม่

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

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

class Solution {
public:
    int minKBitFlips(vector<int>& A, int K) {
        int n = A.size();
        vector<int> moves(n, 0);
        int counter = 0;
        
        for(int i=0; i+K<=n; i++) {
            if(i > 0) moves[i] += moves[i-1];
            int actual = (A[i] + moves[i]) % 2;
            if(actual == 0) {
                moves[i]++;
                if(i+K < n) moves[i+K]--;
                counter++;
            }
        }
        
        for(int i=n-K+1; i 0) moves[i] += moves[i-1];
            if((A[i] + moves[i]) % 2 == 0) return -1;
        }
        return counter;
    }
};

ความซับซ้อน

• เวลา: O(n)
• พื้นที่: O(n)