โปรแกรมนับจำนวนการพลิกสับลิสต์ความยาว K ให้กลายเป็นทั้ง 0 ใน Python

ได้รับลิสต์ nums (0 และ 1) และ k Operation: เลือก sublist ความยาว k พลิกทุกตัว (0↔1) หา จำนวน operation น้อยที่สุด ให้ทั้งลิสต์กลายเป็น 0 ถ้าไม่ได้ → -1

ตัวอย่าง

Input: nums = [1,1,1,0,0,1,1,1], k = 3

Output: 2 (พลิก 3 ตัวแรก และ 3 ตัวท้าย)

แนวทางแก้ปัญหา

ใช้ Greedy + Difference Array (Lazy Propagation):

1. วนซ้ายไปขวา ตัดสินใจที่ i ว่าต้องพลิกเริ่มที่นี่หรือไม่
2. เก็บสถานะ flipped = จำนวนครั้งที่ถูกพลิก (mod 2) สำหรับตำแหน่งปัจจุบัน
3. ใช้ array to_conv mark จุดที่ effect ของการพลิกจบ (i+k)
4. ถ้าค่าปัจจุบัน (หลัง xor flipped) เป็น 1 → ต้องพลิกที่นี่
5. ถ้า i + k > n → ไม่ได้ → return -1

การใช้งาน (Python)

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]      # อัปเดต flipped จาก events ที่จบ
            cur = nums[i] ^ flipped    # ค่าจริงหลังคำนวณ flipped
            
            if cur == 1:
                # ต้องพลิกเริ่มที่ i
                flipped ^= 1
                res += 1
                if i + k > n:
                    return -1
                if i + k < n:
                    to_conv[i + k] = 1  # mark จุดที่ effect จบ
        
        return res

# ทดสอบ
ob = Solution()
print(ob.solve([1,1,1,0,0,1,1,1], 3))  # Output: 2

ความซับซ้อน

• Time Complexity: O(N)
• Space Complexity: O(N)

เทคนิค Difference Array / Lazy Propagation ทำให้ O(1) ต่อการอัปเดต