Chương trình đếm số lần lật mảng con độ dài k để biến toàn bộ thành 0 trong Python

Cho mảng nums chỉ chứa 0/1 và số k. Mỗi phép toán lật một mảng con độ dài k (0→1, 1→0). Tìm số phép tối thiểu để biến toàn bộ thành 0. Không thể → -1.

Ví dụ: nums = [1,1,1,0,0,1,1,1], k=3 → 2 (lật 3 đầu và 3 cuối).

Giải thuật (Greedy + Mảng hiệu difference array)

1. Duyệt trái sang phải, giữ biến flipped (số lần lật ảnh hưởng đến vị trí hiện tại, mod 2).
2. Mảng to_conv đánh dấu vị trí kết thúc tác động của phép lật.
3. Tại i: flipped ^= to_conv[i], giá trị thực cur = nums[i] ^ flipped.
4. Nếu cur == 1: phải lật tại đây → flipped ^= 1, res++, đánh dấu to_conv[i+k] = 1 (nếu trong phạm vi).
5. Nếu i + k > n mà vẫn cần lật → trả về -1.

Ví dụ minh họa

class Solution:
    def solve(self, nums, k):
        n = len(nums)
        res = 0
        flipped = 0
        to_conv = [0] * n
        for i in range(n):
            flipped ^= to_conv[i]
            cur = nums[i] ^ flipped
            if cur == 1:
                flipped ^= 1
                res += 1
                if i + k - 1 >= n:
                    return -1
                if i + k < n:
                    to_conv[i + k] = 1
        return res

ob = Solution()
nums = [1,1,1,0,0,1,1,1]
k = 3
print(ob.solve(nums, k))  # Output: 2

Đầu vào / Đầu ra

Input: [1,1,1,0,0,1,1,1], 3

Output: 2