In an array A containing only 0s and 1s, a K-bit flip consists of choosing a (contiguous) subarray of length K and simultaneously changing every 0 in the subarray to 1, and every 1 in the subarray to 0.
Return the minimum number of K-bit flips required so that there is no 0 in the array.  If it is not possible, return -1.
 
Example 1:
Input: A = [0,1,0], K = 1
Output: 2
Explanation: Flip A[0], then flip A[2].


Example 2:
Input: A = [1,1,0], K = 2
Output: -1
Explanation: No matter how we flip subarrays of size 2, we can't make the array become [1,1,1].


Example 3:
Input: A = [0,0,0,1,0,1,1,0], K = 3
Output: 3
Explanation:
Flip A[0],A[1],A[2]: A becomes [1,1,1,1,0,1,1,0]
Flip A[4],A[5],A[6]: A becomes [1,1,1,1,1,0,0,0]
Flip A[5],A[6],A[7]: A becomes [1,1,1,1,1,1,1,1]

 


Note:

1 <= A.length <= 30000
1 <= K <= A.length

Difficulty: interview

Starter code:

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        

Solutions:
class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        n = len(A)
        record = [0] * n
        flip = 0
        ans = 0
        for i in range(n):
            if i >= K: flip -= record[i-K]
            if A[i] == (flip % 2):
                if i > n - K: return -1
                ans += 1
                flip += 1
                record[i] = 1
        return ans



class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        l = len(A)
        flipped = [0] * l
        res = 0
        flipping_count = 0
        for i in range(l):
            if i >= K:
                flipping_count -= flipped[i - K]
            if (flipping_count % 2 == 0 and A[i] == 0) or (flipping_count % 2 == 1 and A[i] == 1):
                if i + K > l:
                    return -1
                flipped[i] += 1
                flipping_count += 1
                res += 1
                
        return res

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        flip_pos = 0
        flip_inds = []
        for i in range(len(A)):
            # find the correct current bit based on prior flips
            while flip_pos < len(flip_inds) and i - K + 1 > flip_inds[flip_pos]:
                flip_pos += 1
                
            cur_bit = A[i] ^ ((len(flip_inds) - flip_pos) % 2 != 0)
            
            if i > len(A) - K:
                if cur_bit == 0:
                    return -1
            else:
                if not cur_bit:
                    flip_inds.append(i)
                
        return len(flip_inds)

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        ans=flip=0
        N=len(A)
        hint=[0]*N
        for i,x in enumerate(A):
            flip^=hint[i]
            if x^flip==0:
                ans+=1
                if i+K>N: return -1
                flip^=1
                if i+K<N: hint[i+K]^=1
        return ans

class Solution:
    def minKBitFlips(self, A: List[int], k: int) -> int:
        k_bit_flip_end_indices = deque()
        switch = 0
        flips = 0
        for i, bit in enumerate(A):
            if (len(k_bit_flip_end_indices) & 1) ^ bit == 0:
                flips += 1
                k_bit_flip_end_indices.append(i+k-1)
            if k_bit_flip_end_indices and i == k_bit_flip_end_indices[0]:
                k_bit_flip_end_indices.popleft()
        return flips if not k_bit_flip_end_indices else -1

class Solution:
    def minKBitFlips(self, A, K):
        cur = res = 0
        for i in range(len(A)):
            if i >= K and A[i - K] == 2:
                cur -= 1
            if (cur % 2) == A[i]:
                if i + K > len(A):
                    return -1
                A[i] = 2
                cur, res = cur + 1, res + 1
        return res

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        
        count = 0
        stack = []
        for i in range(len(A)):
            if stack and i == stack[0]: 
                stack.pop(0)
            if A[i] == len(stack)%2:
                if i+ K > len(A): return -1
                count += 1
                stack.append(i+K)

        return count 
        
#         start = count = 0
#         while  start < len(A):
#             if not A[start]:
#                 if start + K > len(A): return -1
#                 for i in range(start, start+K):
#                     A[i] = 1 - A[i]
#                 count += 1
#             start += 1
#         return count
            


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        total_flips = 0
        current_effective_flips = 0
        flip_indices = []

        for current_index, elem in enumerate(A):
            if (flip_indices and current_index == flip_indices[0] + K):
                flip_indices.pop(0)
                current_effective_flips -= 1

            if self.needs_flip(elem, current_effective_flips):
                if current_index + K > len(A):
                    return -1
                flip_indices.append(current_index)
                current_effective_flips += 1
                total_flips += 1
        return total_flips

    def needs_flip(self, elem, current_effective_flips):
        return ((elem == 0 and current_effective_flips % 2 == 0) or
                (elem == 1 and current_effective_flips % 2 != 0))

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        store = [0] * len(A)
        ans = flip = 0
        
        
        for i, x in enumerate(A):
            flip ^= store[i]
            if x ^ flip == 0:
                ans += 1
                if i+K > len(A):
                    return -1
                flip ^= 1
                if i + K < len(A):
                    store[i+K] ^= 1
        return ans

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        
        count = 0
        stack = []
        for i in range(len(A)):
            if stack and i == stack[0]: stack.pop(0)
            if A[i] == len(stack)%2:
                if i+ K > len(A): return -1
                count += 1
                stack.append(i+K)

        return count 
        
#         start = count = 0
#         while  start < len(A):
#             if not A[start]:
#                 if start + K > len(A): return -1
#                 for i in range(start, start+K):
#                     A[i] = 1 - A[i]
#                 count += 1
#             start += 1
#         return count
            


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        nums = A
        flip_count = 0
        flip_hint = [0] * len(nums)
        total_flips = 0
        
        for i, n in enumerate(nums):
            if i >= K and flip_hint[i-K]:
                total_flips -= 1
            
            if total_flips % 2 == n:
                if i + K > len(nums):
                    return -1
                
                total_flips += 1
                flip_hint[i] = 1
                flip_count += 1
                
        return flip_count


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        n = len(A)
        ans = 0
        flips = 0
        addon = 6
        m = False
        for i in range(n):
            if A[i] > 5:
                m = True
                A[i] -= addon
            if (flips % 2 == 0 and A[i] == 0) or (flips % 2 != 0 and A[i] == 1):
                ans += 1
                if i + K > n: return -1
                A[i+K-1] += addon
                flips += 1
            if m or A[i] > 5:
                flips -= 1
                A[i] -= addon
                m = False
        return ans

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        res = 0
        flip = 0
        for i in range(len(A)):
            if flip % 2 != 0:
                if A[i] % 10:
                    res += 1
                    flip += 1
                    if (i + K - 1) >= len(A):
                        return -1
                    A[i + K - 1] += 10
            else:
                if not A[i] % 10:
                    res += 1
                    flip += 1
                    if (i + K -1) >= len(A):
                        return -1
                    A[i+K-1] += 10
            if flip > 0 and A[i] > 1:
                flip -= 1
            
            
        return res

from collections import deque
class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        s = deque()
        count = 0
        for i in range(len(A)):
            while s and s[0] + K <= i:
                s.popleft()
            flip = len(s) % 2 == 1
            ok = flip ^ A[i]
            if not ok:
                if i + K > len(A):
                    return -1
                s.append(i)
                count += 1
        return count
                


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        N = len(A)
        hint = [0] * N
        ans = flip = 0

        # When we flip a subarray like A[i], A[i+1], ..., A[i+K-1]
        # we can instead flip our current writing state, and put a hint at
        # position i+K to flip back our writing state.
        for i, x in enumerate(A):
            flip ^= hint[i]
            if x ^ flip == 0:  # If we must flip the subarray starting here...
                ans += 1  # We're flipping the subarray from A[i] to A[i+K-1]
                if i+K > N: return -1  # If we can't flip the entire subarray, its impossible
                flip ^= 1  
                if i+K < N: hint[i + K] ^= 1

        return ans
                


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        cur = res = 0
        for i in range(len(A)):
            if i >= K and A[i - K] == 2:
                cur -= 1
            if (cur % 2) == A[i]:
                if i + K > len(A):
                    return -1
                A[i] = 2
                cur, res = cur + 1, res + 1
        return res

class Solution:
    def minKBitFlips(self, A: List[int], k: int) -> int:
        
        flipped = collections.deque()
        
        # Greedy
        # 1. Never flip a 1
        # 2. Try flipping every 0
        
        flips = 0
        for i in range(len(A)):
            
            if flipped and flipped[0] < i:
                flipped.popleft()
                
            if (not (len(flipped)&1) - A[i]):
                if i <= len(A) - k:
                    flips += 1
                    flipped.append(i+k-1)
                else:
                    return -1
        
        return flips

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        N = len(A)
        hint = [0] * N # Keeps track of whether there has been at least one flip at given index
        counter = 0 # Total flips
        flip = 0 # Whether we are looking at a flipped array or not (follow code in for loop, e.g. 1011)
        for i, x in enumerate(A):
            # Check if bit is known to be flipped. If it is flipped and we are looking at a flipped bit, then we can simply set flip to 0
            flip = (flip + hint[i]) % 2
        
        # If x is 1 and flipped or x is 0 and unflipped, then it is 0, so we need to flip the bit.
            if (x == 1 and flip == 1) or (x == 0 and flip == 0):
                counter += 1  # Add to the flip counter
                
                # Check if K-bit flip goes past end of array.
                if i+K > N:
                    return -1
                
                # We flipped, so we change our flip value for the next iteration of the loop
                flip = 1-flip
                
                # 
                if i+K < N:
                    hint[i + K] = 1

        return counter
                


class Solution:
    def minKBitFlips(self, A, K):
        cur, res, n = 0, 0, len(A)
        for i in range(0,len(A)):
            if i >= K and A[i - K] > 1:
                A[i - K] -= 2
                cur -= 1
            if cur & 1 ^ A[i] == 0:
                if i + K > len(A):
                    return -1
                A[i] += 2
                cur += 1
                res += 1
        return res


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        count = 0
        flippings = [False for _ in A]
        flipped = False
        for i in range(len(A)):
            if flippings[i]:
                flipped = not flipped
            if (not flipped and A[i] == 0) or (flipped and A[i] == 1):
                count += 1
                flipped = not flipped
                if i + K > len(A):
                    return -1
                if i + K < len(flippings):
                    flippings[i + K] = True
                
                
        return count


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        N = len(A)
        hint = [0] * N
        ans = flip = 0

        # when we flip a subarray like A[i], A[i+1], .., A[i+K-1]
        # we can instead flip our current writing state, and put a hint at position i+K to flip back
        # our writing state
        for i, x in enumerate(A):
            flip ^= hint[i]

            # if we must flip the subarray starting here...
            if x ^ flip == 0:
                ans += 1

                if i + K > N: return -1

                flip ^= 1
                if i + K < N: hint[i + K] ^= 1

        return ans

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        flips = 0
        q = deque()
        for i, x in enumerate(A):
            if q and q[0] == i:
                q.popleft()
            if len(q) & 1:
                x ^= 1
            if x == 0:
                flips += 1
                q.append(i + K)
                if i + K > len(A):
                    return -1
        return flips

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        N = len(A)
        hint = [0] * N
        ans = flip = 0

        # When we flip a subarray like A[i], A[i+1], ..., A[i+K-1]
        # we can instead flip our current writing state, and put a hint at
        # position i+K to flip back our writing state.
        for i, x in enumerate(A):
            flip ^= hint[i]
            if x ^ flip == 0:  # If we must flip the subarray starting here...
                ans += 1  # We're flipping the subarray from A[i] to A[i+K-1]
                if i+K > N: return -1  # If we can't flip the entire subarray, its impossible
                flip ^= 1  
                if i+K < N: hint[i + K] ^= 1

        return ans

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        cur, res, n = 0, 0, len(A)
        for i in range(len(A)):
            if i >= K and A[i - K] > 1:
                A[i - K] -= 2
                cur -= 1
            if cur & 1 ^ A[i] == 0:
                if i + K > len(A):
                    return -1
                A[i] += 2
                cur += 1
                res += 1
        return res

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        n = len(A)
        flip = 0
        current_flips = 0
        queue = []
        for i in range(n):

            if len(queue)>0 and queue[0] + K == i:
                queue.pop(0)
                current_flips = current_flips - 1
                
            if (A[i] == 0 and current_flips %2 == 0) or (A[i] == 1 and current_flips %2 != 0):
                if i + K > n:
                    return -1
                queue.append(i)
                current_flips = current_flips +1
                flip = flip + 1

        return flip

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        cur = res = 0
        for i in range(len(A)):
            if i >= K and A[i - K] == 2:
                cur -= 1
            if cur % 2 == A[i]:
                if i + K > len(A):
                    return -1
                A[i] = 2
                cur, res = cur + 1, res + 1
        return res

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        flipped = deque()
        count = 0
        flips = 0
        
        for i in range(len(A)):
            if i > 0:
                x = flipped.popleft() if i >= K else 0
                count -= x

            if (A[i] + count) % 2 == 0:
                count += 1
                flipped.append(True)
                flips += 1
            else:
                flipped.append(False)
                
        return flips if not any(list(flipped)[1:]) else -1

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        num = 0
        for a in A:
            num = (num << 1) + a
        
        i = 0
        pattern = (1 << K) - 1
        flips = 0
        while i + K <= len(A):
            while i + K <= len(A) and (num & (1 << i)):
                i += 1
            
            if i + K > len(A):
                break
                
            num ^= pattern << i
            flips += 1
            i += 1
        
        if num == (1 << len(A)) - 1:
            return flips
        return -1


class Solution:
    def minKBitFlips(self, A: List[int], k: int) -> int:
        q = collections.deque()
        res = 0
        for i in range(len(A)):
            if len(q) % 2 == 0:
                if A[i] == 0:
                    res += 1
                    q.append(i + k - 1)
            else:
                if A[i] == 1:
                    res += 1
                    q.append(i + k - 1)
            if q and q[0] == i: q.popleft()
            if q and q[-1] >= len(A): return -1
        return res

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        # left bit needs to get flipped
        # flip left bit and the K-1 bits to the right
        # now consider
        
#         counter = 0
#         for i in range(len(A)-K+1):
#             # print(i,A)
#             if A[i] == 0:
#                 counter += 1
#                 for j in range(K):
#                     A[i+j] ^= 1
            
#         # return counter if sum(A) == len(A) else -1
#         return counter if 0 not in A[-K:] else -1
            
        counter = 0
        q = []
        qL = 0
        
        for i in range(len(A)-K+1):
            if A[i] == (len(q)-qL) % 2: # then this bit would be a 0 after previous flips applied
                # flip at A[i]
                counter += 1
                q.append(i+K-1) # the last bit affected by this flip
            if qL < len(q) and q[qL] == i:
                qL += 1
            # print(q)
            # print(f'i:{i}, qL:{qL}, len(q), {len(q)}, top')
        
        # check the bits for which there's not enough room to flip at
        for i in range(len(A)-K+1, len(A)):
            
            if A[i] == (len(q)-qL) % 2:
                # 0 0, 1 1
                return -1
            if qL < len(q) and q[qL] == i:
                qL += 1
            # print(q)
            # print(f'i:{i}, qL:{qL}, len(q), {len(q)}, top')
                    
        return counter

class Solution:
    def minKBitFlips(self, A: 'List[int]', K: 'int') -> 'int':
        flip = 0
        const = 10
        res = 0
        for i in range(len(A)):
            if flip % 2 != 0:
                if A[i] % 10:
                    res += 1
                    flip += 1
                    if i + K - 1 >= len(A):
                        return -1
                    A[i + K - 1] += const
            else:
                if not A[i] % 10:
                    res += 1
                    flip += 1
                    if i + K - 1 >= len(A):
                        return -1
                    A[i + K - 1] += const
            if A[i] > 1:
                flip -= 1
        return res

from collections import deque

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        flipped = 0
        q = deque()
        flips = 0
        for i in range(len(A)):
            if len(q) == K:
                flipped ^= q.popleft()
            
            if flipped == A[i]:
                if i + K > len(A):
                    return -1
                flipped ^= 1
                flips += 1
                q.append(1)
            else:
                q.append(0)
        
        return flips


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        interval_status = [ 0 ] * (len(A) + 1)
        counter = 0
        prev = 0
        for i in range(len(A)):
            prev ^= interval_status[i]
            curr_status = prev ^ A[i] 
            # print(curr_status)
            if curr_status == 0:
                if i + K <= len(A):
                    interval_status[i + K] ^= 1
                    counter += 1
                    prev ^= 1
                    
                else:
                    return -1
            
        return counter

class Solution:
    def minKBitFlips(self, A: 'List[int]', K: 'int') -> 'int':
        flip = 0
        const = 10
        res = 0
        for i in range(len(A)):
            temp = A[i] % 10
            if flip % 2 != 0:
                if temp:
                    res += 1
                    flip += 1
                    if i + K - 1 < len(A):
                        A[i + K - 1] += const
                    else:
                        return -1
            else:
                if not temp:
                    res += 1
                    flip += 1
                    if i + K - 1 < len(A):
                        A[i + K - 1] += const
                    else:
                        return -1
            if A[i] > 1:
                flip -= 1
        return res

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        q = deque()
        res = 0
        for i in range(len(A)):
          if len(q) % 2 != 0: # means even numbers of flip
            if A[i] == 1: # flip to 0
              res += 1
              q.append(i+K-1)
          else:
            if A[i] == 0:
              res += 1
              q.append(i+K-1)
          if q and q[0] == i:
            q.popleft()
          if q and q[-1] >= len(A):
            return -1
        return res

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        
        n = len(A)
        ff = [0 for i in range(n)]
        
        
        
        cur = 0
        f = 0
        for i in range(n):
            
            cur += ff[i]
            xo = cur % 2
            if xo ^ A[i] == 0:
                if i + K - 1 > n - 1:
                    return -1
                else:
                    f += 1
                    ff[i] += 1
                    if i + K < n:
                        ff[i + K] -= 1
                    cur += 1
        return f

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        res = 0
        queue = collections.deque([])
        
        for i in range(len(A)):
            while queue and queue[0] < i:
                queue.popleft()
            
            if (A[i] + len(queue)) % 2 == 0:
                if i+K-1 >= len(A):
                    return -1
                else:
                    queue.append(i+K-1)
                    res += 1
                    
        return res

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        flipped = [0] * len(A)
        p = ans = 0
        for i in range(len(A)):
            if i >= K:
                # switch back
                p ^= flipped[i - K]
            if p == A[i]:
                if i + K > len(A):
                    return -1
                ans += 1
                flipped[i] = 1
                p ^= 1
        return ans

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        res = 0
        flip = 0
        na = [0]*len(A)
        for i,x in enumerate(A):
            flip ^= na[i]
            if flip ^ x == 0:
                res += 1
                flip ^= 1
                if i+ K > len(A):
                    return -1
                if i+ K < len(A):
                    na[i+K] ^= 1
        return res

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        n = len(A)
        flip_count = 0
        hint = [0] * n
        min_flip = 0
        
        for i in range(n):
            if i >= K and hint[i-K] == 1:
                flip_count -= 1
            
            if flip_count % 2 == A[i]:
                if i + K > n:
                    return -1
                
                min_flip += 1
                flip_count += 1
                
                hint[i] = 1
                
        return min_flip


from collections import deque
class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        reduceInds = deque()
        if K == 1:
            return len(A) - sum(A)
        
        maxFlipCnt = 0
        effectiveFlipCnt = 0
        for i,b in enumerate(A):
            if len(reduceInds) != 0 and reduceInds[0] == i:
                effectiveFlipCnt -= 1
                reduceInds.popleft()
            
            if b == 0 and effectiveFlipCnt % 2 == 0 or b == 1 and effectiveFlipCnt % 2 == 1:
                if i >= len(A) - K + 1: # No way to flip now, just check if it is 0
                    return -1
                else:
                    maxFlipCnt+=1
                    effectiveFlipCnt+=1
                    reduceInds.append(i + K)
        
        return maxFlipCnt
        
                
        


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        q = collections.deque()
        res = 0
        for i in range(len(A)):
            if A[i] == len(q) % 2:
                q.append(i)
                res += 1
            
            if q and q[0] <= i - K + 1:
                q.popleft()
        return res if len(q) == 0 else -1

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        dq = deque()
        res = 0
        for i in range(len(A)):
            if A[i] == len(dq) % 2:
                res += 1
                dq.append(i+K-1)
                
            if dq and dq[0] <= i:
                dq.popleft()
                
        return res if not dq else -1

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        N = len(A)
        flipped = [0 for _ in range(N)]
        curr = 0
        ans = 0
        for i in range(N):
            if i >= K:
                curr ^= flipped[i - K]
            if curr == A[i]:
                if i + K > N:
                    return -1
                flipped[i] = 1
                curr ^= 1
                ans += 1
        return ans

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        res = 0
        q = deque()
        for i in range(len(A)):
            if len(q) % 2 != 0:
                if A[i] == 1:
                    res += 1
                    q.append(i + K - 1)
            else:
                if A[i] == 0:
                    res += 1
                    q.append(i + K - 1)
            if q and q[0] == i:
                q.popleft()
            if q and q[-1] >= len(A):
                return -1
        return res


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        flips = collections.deque()
        res = 0
        for i, a in enumerate(A):
            if (A[i] == 0 and not len(flips) & 1) or (A[i] != 0 and len(flips) & 1):
                res += 1
                flips.append(i + K - 1)
            while flips and flips[0] <= i:
                flips.popleft()
        return res if not flips else -1


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        cnt=0
        dq=collections.deque()
        for i in range(len(A)):
            if A[i]==(1 if len(dq)%2 else 0):
                cnt+=1
                dq.append(i+K-1)
            if dq and dq[0]==i:
                dq.popleft()
        return -1 if len(dq) else cnt


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        flips = collections.deque()

        result = 0
        for i, num in enumerate(A):
            if A[i] == (len(flips) & 1):
                result += 1
                flips.append(i + K - 1)
            while flips and flips[0] <= i:
                flips.popleft()

        return result if len(flips) == 0 else -1


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        cur, res = 0 ,0
        for i in range(len(A)):
            if i >= K and A[i-K] > 1:
                cur -= 1
                A[i-K] -= 2
            if cur % 2 == A[i]:
                if i + K > len(A):
                    return -1
                A[i] += 2
                res += 1
                cur += 1
        return res
                


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        res, flipped, isFlipped = 0, 0, [0] * len(A)
        
        for i in range(len(A)):
            if i >= K:
                flipped ^= isFlipped[i - K]
            if not A[i] ^ flipped:
                if i + K > len(A): return -1
                isFlipped[i] ^= 1
                res += 1
                flipped ^= 1
        
        return res
                
        
        


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        i=0
        c=0
        q=collections.deque()
        
        sign=0
        while True:
            while i<len(A) and A[i]!=sign:
                i+=1
                if q and i==q[0]:
                    q.popleft()
                    sign=1-sign
                    
            if i==len(A):
                return c
             
            if i+K>len(A):
                return -1
            
            q.append(i+K)
            sign=1-sign
            
            c+=1
            i+=1
            if q and i==q[0]:
                q.popleft()
                sign=1-sign
                
        return c
    
    
            
            
                


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        flip_time=0
        n=len(A)
        close=[False for i in range(n)]
        #print(close)
        res=0
        for i in range(n):
            if close[i]:
                flip_time-=1
            if (A[i]==0 and flip_time%2==0) or (A[i]==1 and flip_time%2==1):
                flip_time+=1
                res+=1
                if i+K>n: return -1
                if i+K<n:
                    close[i+K]=True
        return res
                
                
        


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        flips = 0
        carry = 10
        result = 0
        valid = True
        for i, num in enumerate(A):
            if (A[i] & 1) == (flips & 1):
                result += 1
                flips += 1
                if i < len(A) - K + 1:
                    A[i + K - 1] += carry
                else:
                    valid = False
            if A[i] > 1:
                A[i] -= carry
                flips -= 1

        return result if valid else -1


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        l = len(A)
        rem = l % K
        # find indexes where the number changes
        # add to change_list based on remainder class mod K
        prev = 1
        change_list = [[] for i in range(K)]
        for ind, num in enumerate(A):
            if prev != num:
                prev = num
                change_list[ind % K].append(ind)
        if num == 0:
            change_list[rem].append(l)
    
        num_flips = 0
        
        for r, mini_list in enumerate(change_list):
            mini_list_len = len(mini_list)
            if mini_list_len % 2 == 1:
                return -1
            for i in range(mini_list_len // 2):
                first = mini_list.pop(0)
                second = mini_list.pop(0)
                num_flips += (second - first) // K
        
        return num_flips
        
        
        
        
    
    
    def oldMinKBitFlips(self, A: List[int], K: int) -> int:
        l = len(A)
        
        # find indexes where the number changes
        prev = 1
        change_list = []
        for ind, num in enumerate(A):
            if prev != num:
                prev = num
                change_list.append(ind)
        
        if len(change_list) == 0:
            return 0
        
        num_flips = 0

        while len(change_list) > 1:
            first = change_list[0]
            # if first + K > l, we are doomed
            if first + K >= l:
                return -1
            # remove first, and either
                # 1) remove first + K if it exists, or
                # 2) add first + K if it does not exist
            change_list = change_list[1:]
            left_insertion_pt = bisect.bisect_left(change_list, first + K)
            if left_insertion_pt >= len(change_list):
                change_list.append(first + K)
            elif change_list[left_insertion_pt] == first + K:
                del change_list[left_insertion_pt]
            else:
                change_list.insert(left_insertion_pt, first+K)
            num_flips += 1
            
            
        if len(change_list) > 0:
            # in this section, len(change_list) == 1
            first = change_list[0]
            q, r = divmod(l - first, K)
            if r == 0:
                return num_flips + q
            else:
                return -1
            
        return num_flips

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        n = len(A)
        cur = 0 # 到达当前位置的翻转次数
        res = 0
        for i in range(n):
            if i >= K and A[i-K] > 1:
                # 最左元素被移除窗口，所以要取消它的翻转
                cur -= 1
                A[i-K] -= 2
            if (cur % 2) == A[i]: # 翻转次数与A[i]同奇偶就需要翻转
                if i + K > n: return -1
                cur += 1
                res += 1
                A[i] += 2
        return res


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        i=0
        c=0
        q=collections.deque()
        sign=0
        
        for i in range(len(A)):
            
            if q and i==q[0]:
                sign=1-sign
                q.popleft()
            
            if A[i]!=sign:
                continue
            else:
                if i+K>len(A):
                    return -1
                
                q.append(i+K)
                sign=1-sign
                c+=1
                
        return c
    
    
            
            
                


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        flips = collections.deque()
        cnt = 0
        for i in range(len(A)):
            while flips and flips[0] <= i - K:
                flips.popleft()
            curtStatus = A[i] + len(flips)
            
            if curtStatus % 2 == 0:
                if i > len(A) - K:
                    return -1
                else:
                    flips.append(i)
                    cnt += 1
        return cnt
            




class Solution(object):
    def minKBitFlips(self, A, K):
        # https://www.youtube.com/watch?v=tbNpHv2HDXo
        cur = res = 0
        for i in range(len(A)):
            if i >= K and A[i - K] == 2:
                cur -= 1
            if (cur % 2) == A[i]:
                if i + K > len(A):
                    return -1
                A[i] = 2
                cur, res = cur + 1, res + 1
        return res



class Solution1:
    def minKBitFlips(self, A, K):
        cur, res, n = 0, 0, len(A)
        for i in range(len(A)):
            if i >= K and A[i - K] > 1:
                A[i - K] -= 2
                cur -= 1
            if cur & 1 ^ A[i] == 0:
                if i + K > len(A):
                    return -1
                A[i] += 2
                cur += 1
                res += 1
        return res


# class Solution:
#     def minKBitFlips(self, A: List[int], K: int) -> int:
#         cnt = 0
#         for i in range(len(A) + 1 - K):
#             if A[i] == 0:
#                 cnt += 1
#                 for k in range(K):
#                     A[i+k] ^= 1
#             else:
#                 continue 
#         return cnt if 0 not in A[-K:] else -1


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        # greedy
        n = len(A)
        flipped = res = 0
        isFlipped = [0] * n
        for i in range(n):
            # isFlipped[i-K] does not affect i here
            if (i >= K):
                flipped ^= isFlipped[i-K]
            if (flipped ^ A[i] == 0):
                if (i + K > n):
                    return -1
                isFlipped[i] = 1
                flipped ^= 1
                res += 1
        
        return res


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        flips = collections.deque()
        res = 0
        for i, a in enumerate(A):
            if (A[i] != 0 and len(flips) & 1) or (not len(flips) & 1 and A[i] != 1):
                res += 1
                flips.append(i + K - 1)
            while flips and flips[0] <= i:
                flips.popleft()
        return res if not flips else -1
                
        
        
        
#         flips = collections.deque()
#         res = 0
#         for i, a in enumerate(A):
#             if (A[i] != 0 and len(flips) & 1) or (not len(flips) & 1 and A[i] != 1):
#                 res += 1
#                 flips.append(i + K - 1)
#             while flips and flips[0] <= i:
#                 flips.popleft()
#         return res if not flips else -1
                


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        flips = collections.deque()
        res = 0
        for i, a in enumerate(A):
            if (A[i] != 0 and len(flips) & 1) or (not len(flips) & 1 and A[i] != 1):
                res += 1
                flips.append(i + K - 1)
            while flips and flips[0] <= i:
                flips.popleft()
        return res if not flips else -1
                


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        '''greedy+ 滑动窗口
        1.用deque保存反转过的idx，长度就是总共能管到i的反转次数
          start往后走的时候队头不在当前window的出站
          [0,0,0,1,0,1,1,0]
                         i
           que = [5]
           len == 1 => flipped  res += (len(que) %2 ^ A[i] == 0)
           res = 3
        2. 用count表示window里面flip了多少次(或者就用count的mod)
           flip的用A[i]-2 => 0:-2, 1:-1 来做mark这样start出window的时候才能减去count
           出window的时候把2加回去=> -2:0, -1:1
        '''
        start = 0
        count = 0
        res = 0
        for end, a in enumerate(A):
            if count ^ A[end] == 0: #(count % 2)^ A[end]
                #print(end)
                A[end] -= 2
                res += 1
                count ^= 1 # count++
                
            if end >= start + K - 1: #move window start
                if A[start] < 0:
                    count ^= 1 #count--
                    A[start] += 2 #flip back
                start += 1
        #print(A)  
        # at the end if there is anything not flipped? (last window need flip)
        return -1 if any([a < 0 for a in A]) else res

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        '''greedy+ 滑动窗口
        1.用deque保存反转过的idx，长度就是总共能管到i的反转次数
          start往后走的时候队头不在当前window的出站
          [0,0,0,1,0,1,1,0]
                         i
           que = [5]
           len == 1 => flipped  res += (len(que) %2 ^ A[i] == 0)
           res = 3
        2. 用count表示window里面flip了多少次(或者就用count的mod)
           flip的用A[i]-2 => 0:-2, 1:-1 来做mark这样start出window的时候才能减去count
           出window的时候把2加回去=> -2:0, -1:1
        '''
        start = 0
        count = 0
        res = 0
        for end, a in enumerate(A):
            if count ^ A[end] == 0: #(count % 2) ^ A[end]
                #print(end)
                A[end] -= 2
                res += 1
                count ^= 1 # count++
                
            if end >= start + K - 1: #move window start
                if A[start] < 0: #被flip过
                    count ^= 1 #count-- #这个start影响不到end了
                    A[start] += 2 #flip back
                start += 1
        #print(A)  
        # at the end if there is anything not flipped? (last window need flip)
        return -1 if any([a < 0 for a in A]) else res

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        N = len(A)
        flips = []
        res, total = 0, 0
        for i, v in enumerate(A):
            if i < N - K + 1:
                if v == 1:
                    if total & 1:
                        total += 1
                        res += 1
                        flips.append(1)
                    else:
                        flips.append(0)
                else:
                    if total & 1:
                        flips.append(0)
                    else:
                        total += 1
                        res += 1
                        flips.append(1)
            else:
                if v == 0:
                    if not total & 1:
                        return -1
                if v == 1:
                    if total & 1:
                        return -1
            if i >= K - 1:
                total -= flips[i-K+1]
        return res


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        # 谷歌面经。给定你一个01序列。然后每次可以连续K个数进行翻转。问你最少操作次数使得全0
        # 这道题是一道贪心题。因为A[0]翻转不翻转只有唯一的一个办法。
        # 空间上考虑A只有01元素。因此可以利用这个特点避免使用额外空间
        cur, res, n = 0, 0, len(A)
        # cur means the numbers of flips in the current sliding window of size K
        # in the window, if the cur is even and A[i] = 0,we need to flip
        # if the cur is odd and A[i] = 1,we need to flip
        # we want to flip A[i], from 0 to 2, from 1 to 3.when go out window, we change it back
        for i in range(n):
            if i >= K and A[i - K] > 1:
                A[i - K] -= 2
                cur -= 1   # 维持滑动窗口
            if (cur & 1) ^ A[i] == 0:  # 根据前面的分析，这个时候我们需要替换当前的A[i]
                if i + K > len(A):   # 不过此时有一个特别注意，那就是超界（没有等号）
                    return -1
                A[i] += 2
                cur += 1
                res += 1
        # print(A)  最后窗口内的还是没完全改回来，不过问题不大
        return res

class Solution(object):
    def minKBitFlips(self, A, K):
        N = len(A)
        hint = [0] * N
        ans = flip = 0

        # When we flip a subarray like A[i], A[i+1], ..., A[i+K-1]
        # we can instead flip our current writing state, and put a hint at
        # position i+K to flip back our writing state.
        for i, x in enumerate(A):
            flip ^= hint[i]
            if x ^ flip == 0:  # If we must flip the subarray starting here...
                ans += 1  # We're flipping the subarray from A[i] to A[i+K-1]
                if i+K > N: return -1  # If we can't flip the entire subarray, its impossible
                flip ^= 1  
                if i+K < N: hint[i + K] ^= 1

        return ans

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        i = 0
        ans = 0
        flips = 0
        dq = collections.deque()
        while i < len(A):
            while dq and i >= dq[0]:
                dq.popleft()
                flips -= 1
            if (A[i] + flips) %2 == 1:
                i += 1
            else:
                if i + K > len(A):
                    return -1
                dq.append(i+K)
                flips += 1
                i += 1
                ans += 1
        return ans
                


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        # intuitive idea: for current position, if it flips, 
        # then we record the right-hand-side farest point that current flip will effect to (whick is i+K-1)
        # call this 'forward propogation'
        # on the other hand, at current position, we need to decite whether we need to flip it or not,
        # this time, we need to look at \"backward propogation\": 
        # the flips that happended historically and still effect current i-th position:
        # 1. if there are even flips effect current i, then when A[i]=0, we need a new flip
        # 2. if there are odd flips effect current i, then only when A[i]=1, we need a new flip
        # when we perform this flip, we will append a new right-hand-side boundary (i+K-1) to current queue:

        # time complexity = O(n) and space complexity = O(K)
        flips = collections.deque() # alike a sliding window, that store the active flips 
        # (which effect current i-th position)

        res = 0
        for i in range(len(A)):
            if A[i] == (len(flips) % 2):
                res += 1
                flips.append(i+K-1)

            if flips and flips[0] <= i: # the head of the queue will not effect i+1 th position, so we pop it
                flips.popleft()
        return res if not flips else -1


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        flipped = [0] * len(A)
        res = 0
        flip = 0
        for i in range(len(A)):
            if i >= K: flip ^= flipped[i - K] #
            if A[i] ^ flip == 0: #
                if i + K > len(A): return -1 #
                res += 1 
                flip ^= 1 
                flipped[i] = 1 
        return res

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        n = len(A)
        D = [0] * n
        D[0] = A[0]
        for i in range(n - 1):
            D[i + 1] = A[i + 1] ^ A[i]
        
        D.append(0)
        cnt = 0
        if D[0] == 0:
            cnt += 1
            D[0] ^= 1
            D[K] ^= 1
        
        for i in range(1, n - K + 1):
            if D[i] == 1:
                cnt += 1
                D[i] ^= 1
                D[i + K] ^= 1
        
        D.pop()
        if D == [1] + [0] * (n - 1):
            return cnt
        else:
            return -1

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        n = len(A)
        flips = [0] * n
        flip = 0
        ans = 0
        
        def mapping(a: int, flip: int) -> int:
            return 1 - a if flip % 2 == 1 else a
            
        for i, a in enumerate(A):
            flip += flips[i]
            if mapping(a, flip) == 0:
                if i + K - 1 < n:
                    ans += 1
                    flips[i] += 1
                    flip += 1
                    A[i] = 1
                    if i + K < n:
                        flips[i + K] -= 1
                else:
                    return -1
        return ans

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        q = collections.deque()
        res = 0
        for i, num in enumerate(A):
            while len(q) > 0 and i - q[0] >= K:
                q.popleft()
            
            if len(q) % 2 == 1 and num == 1 or len(q) % 2 == 0 and num == 0:
                if i + K > len(A):
                    return -1
                q.append(i)
                res += 1
        return res

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        # When we flip a subarray, let's call the set of indices we flipped an interval.
        # When we flip an interval starting at i, we create a hint for a closing event at i+K telling us to flip our writing state back.
        
        N = len(A)
        hint = [0]*N
        ans = flip = 0
        
        # When we flip a subarray like A[i], A[i+1], ..., A[i+K-1]
        # we can instead flip our current writing state, and put a hint at
        # position i+K to flip back our writing state.
        
        for i, x in enumerate(A):
            flip ^= hint[i]
            if x^flip == 0:
                ans += 1
                if i + K > N:
                    return -1
                flip ^= 1
                if i + K < N:
                    hint[i+K] ^= 1
        return ans

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        latest_possible_flip = len(A) - K       # 4
        flipped = collections.deque()
        flips = 0
        for i in range(len(A)):
            if flipped and (flipped[0] < i):    # 3
                flipped.popleft()
            if len(flipped)&1 == A[i]:          # 2
                if i <= latest_possible_flip:   # 4
                    flips += 1
                    flipped.append(i+K-1)       # 1
                else:
                    return -1
        return flips
                


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        flipped = [False] * len(A)
        count = [0] * len(A)
        flips = 0
        
        for i in range(len(A)):
            if i > 0:
                x = flipped[i - K] if i >= K else 0
                count[i] = count[i - 1] - x
            
            if (A[i] + count[i]) % 2 == 0:
                count[i] += 1
                flipped[i] = True
                flips += 1
        #print(flipped)
        #print(count)
        return flips if not any(flipped[len(A) - K + 1:]) else -1

class Solution:
    def minKBitFlips(self, A: List[int], k: int) -> int:
        c=0
        flippedtill=[0 for i in range(len(A)+1)]
        curr=0
        if(len(A)==k):
            if(sum(A)==0):
                return 1
            elif(sum(A)==len(A)):
                return 0
            else:
                return -1
        for i in range(len(A)-k+1):
            curr=(curr+flippedtill[i])%2
            if((A[i]+curr)%2==0):
                flippedtill[i+1]+=1
                flippedtill[i+k]-=1
                c+=1
        for i in range(len(A)-k+1,len(A)):
            curr=(curr+flippedtill[i])%2
            if((A[i]+curr)%2==0):
                return -1
        return c    


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        
        count = 0
        stack = []
        for i in range(len(A)):
            if stack and i == stack[0]:
                stack.pop(0)
           
            if A[i] == len(stack)%2:
                if i+ K > len(A): return -1
                count += 1
                stack.append(i+K)

        return count 
        
#         start = count = 0
#         while  start < len(A):
#             if not A[start]:
#                 if start + K > len(A): return -1
#                 for i in range(start, start+K):
#                     A[i] = 1 - A[i]
#                 count += 1
#             start += 1
#         return count
            




class Solution:
    def minKBitFlips(self, A, K):
        cur, res, n = 0, 0, len(A)
        for i in range(len(A)):
            if i >= K and A[i - K] > 1:
                A[i - K] -= 2
                cur -= 1
            if cur & 1 ^ A[i] == 0:
                if i + K > len(A):
                    return -1
                A[i] += 2
                cur += 1
                res += 1
        return res


# class Solution:
#     def minKBitFlips(self, A: List[int], K: int) -> int:
#         cnt = 0
#         for i in range(len(A) + 1 - K):
#             if A[i] == 0:
#                 cnt += 1
#                 for k in range(K):
#                     A[i+k] ^= 1
#             else:
#                 continue 
#         return cnt if 0 not in A[-K:] else -1


class Solution:
    def minKBitFlips(self, A: List[int], k: int) -> int:

        latest_possible_flip = len(A) - k       # 4
        flipped = collections.deque()
        flips = 0
        for i in range(len(A)):
            if flipped and (flipped[0] < i):    # 3
                flipped.popleft()
            if len(flipped)&1 == A[i]:          # 2
                if i <= latest_possible_flip:   # 4
                    flips += 1
                    flipped.append(i+k-1)       # 1
                else:
                    return -1
        return flips


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        # to maintain a queue to record the position where flip happens in the k window that ends at the current position
        win = collections.deque()
        ans = 0
        for i,x in enumerate(A):
            while len(win)>0 and win[0]<i-K+1:
                win.popleft()
            if (x ^ (len(win)%2) ) ==0  :  # if there are even number of flips and x == 0, need to flip, odd and x==1
                if i+K-1<=len(A)-1:
                    ans += 1
                    win.append(i)
                else:
                    return -1
        return ans



class Solution(object):
    def minKBitFlips(self, A, K):
        '''
        Input: A = [0,0,0,1,0,1,1,0], K = 3
        Output: 3
        Explanation:
        Flip A[0],A[1],A[2]: A becomes [1,1,1,1,0,1,1,0]
        Flip A[4],A[5],A[6]: A becomes [1,1,1,1,1,0,0,0]
        Flip A[5],A[6],A[7]: A becomes [1,1,1,1,1,1,1,1]
        '''
        #https://www.youtube.com/watch?v=tbNpHv2HDXo
        cur = res = 0
        for i in range(len(A)):
            if i >= K and A[i - K] == 2:
                cur -= 1
            if (cur % 2) == A[i]:
                if i + K > len(A):
                    return -1
                A[i] = 2
                cur, res = cur + 1, res + 1
        return res



class Solution1:
    def minKBitFlips(self, A, K):
        cur, res, n = 0, 0, len(A)
        for i in range(len(A)):
            if i >= K and A[i - K] > 1:
                A[i - K] -= 2
                cur -= 1
            if cur & 1 ^ A[i] == 0:
                if i + K > len(A):
                    return -1
                A[i] += 2
                cur += 1
                res += 1
        return res


# class Solution:
#     def minKBitFlips(self, A: List[int], K: int) -> int:
#         cnt = 0
#         for i in range(len(A) + 1 - K):
#             if A[i] == 0:
#                 cnt += 1
#                 for k in range(K):
#                     A[i+k] ^= 1
#             else:
#                 continue 
#         return cnt if 0 not in A[-K:] else -1


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        N = len(A)
        
        hint = [0] * N # Keeps track of first index after a flip
        
        counter = 0 # Total flips
        
        flip = 0 # Whether we are looking at a flipped array or not
        
        for i, x in enumerate(A):
            # If hint[i] == 1, then the flip whose last index was i-1 must be removed from our flip counter
            flip = (flip + hint[i]) % 2
        
        # If x is 1 and flipped or x is 0 and unflipped, then it is 0, so we need to flip the bit.
            if (x == 1 and flip == 1) or (x == 0 and flip == 0):
                counter += 1  # Add to the flip counter
                
                # Check if K-bit flip goes past end of array.
                if i+K > N:
                    return -1
                
                # We flipped, so we change our flip value for the next iteration of the loop
                flip = 1-flip
                
                # Keep track of first index after flip
                if i+K < N:
                    hint[i + K] = 1

        return counter
                


class Solution:
    def minKBitFlips(self, A: List[int], k: int) -> int:
        n = len(A)
        count = [0] * n
        ps = 0
        res = 0
        
        for i in range(n-k+1):
            flip = ps + A[i]
            if flip % 2 == 0:
                count[i] = 1
                res += 1
                ps += 1
            
            if i - k + 1 >= 0:
                ps -= count[i-k+1]
        
        
        for i in range(n-k+1, n):
            if (ps + A[i]) % 2 == 0:
                return -1
            ps -= count[i-k+1]
        
        return res

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        flip_ends = deque()
        count = 0
        for (idx, bit) in enumerate(A):
            if len(flip_ends) > 0 and idx >= flip_ends[0]:
                flip_ends.popleft()
            val = (bit + len(flip_ends)) % 2
            if val == 1:
                continue

            if idx + K > len(A):
                return -1

            count += 1
            flip_ends.append(idx + K)

        return count


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        N = len(A)
        
        flip_ind = [0] * N # Keeps track of first index after a flip
        
        counter = 0 # Total flips
        
        flip = 0 # Flip counter. The flip counter only matters modulo 2.
        
        for i, x in enumerate(A):
            # If flip_ind[i] == 1, then the flip whose last index was i-1 must be removed from our flip counter
            flip = (flip + flip_ind[i]) % 2
        
            # If x is 1 and flipped or x is 0 and unflipped, then it is 0, so we need to flip the bit.
            if (x == 1 and flip == 1) or (x == 0 and flip == 0):
                counter += 1  # Add to the flip counter
                
                # Check if K-bit flip goes past end of array.
                if i+K > N:
                    return -1
                
                # We flipped, so we change our flip value for the next iteration of the loop
                flip = 1-flip
                
                # Keep track of first index after flip
                if i+K < N:
                    flip_ind[i + K] = 1

        return counter
                


class Solution:
    def minKBitFlips(self, A, K: int) -> int:
        flipped, res = 0, 0
        length = len(A)
        isFlipped = [0]*length
        for i, v in enumerate(A):
            if i >= K:
                flipped ^= isFlipped[i-K]
            if flipped == v:
                if i + K > length:
                    return -1
                isFlipped[i] = 1
                flipped ^= 1
                res += 1
        return res

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        is_flipped = [0] * len(A)
        flipped = result = 0
        
        for i in range(len(A)):
            if i >= K:
                flipped ^= is_flipped[i-K]
            
            if A[i] == flipped:
                if i + K > len(A):
                    return -1
                is_flipped[i] = 1
                flipped ^= 1
                result += 1
                
        return result


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        cur, res = 0, 0
        
        for i in range(len(A)):
            # to check if A[i-K] has been flipped
            if i >= K and A[i-K] > 1:
            # since i-K is out of the sliding window, need to substract the total flip number by 1
                cur -= 1
                
            if (cur%2)^A[i] == 0:
                if i + K > len(A):
                    return -1
                
                A[i] += 2
                cur += 1
                res += 1
                
        return res


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        ALen = len(A)
        flips = []
        prevF = 0
        ans = 0
        l = 0
        for i, num in enumerate(A):
            temp = 0
            while l+temp < len(flips) and flips[l+temp] + K- 1 < i:
                temp += 1
            l += temp
            prevF = prevF - temp
            if (prevF%2 and num == 0) or (prevF%2 == 0 and num == 1):
                continue
            else:
                ans += 1
                prevF += 1
                flips.append(i)
            #         if num == 0:
            #         continue
            #     else:
            #         ans += 1
            #         prevF += 1
            #         flips.append(i)
            # else:
            #     if num == 0:
            #         ans += 1
            #         prevF += 1
            #         flips.append(i)
            #     else:
            #         continue
        if flips != [] and flips[-1] + K -1 >= ALen:
            return -1
        return ans

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        cur, res = 0, 0
        
        for i in range(len(A)):
            if i >= K and A[i-K] > 1:
                cur -= 1
                #A[i-K] -= 2
                
            if (cur%2)^A[i] == 0:
                if i + K > len(A):
                    return -1
                
                A[i] += 2
                cur += 1
                res += 1
                
        return res


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        cur, res = 0, 0
        
        for i in range(len(A)):
            # to check if A[i-K] has been flipped
            if i >= K and A[i-K] > 1:
                # as i-K is out of the sliding window, need to substract the total flip number by 1
                cur -= 1
                
            if (cur%2)^A[i] == 0:
                if i + K > len(A):
                    return -1
                
                A[i] += 2
                cur += 1
                res += 1
                
        return res


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        flip_pos = 0
        flip_inds = []
        for i in range(len(A)):
            # find the correct current bit based on prior flips
            while flip_pos < len(flip_inds) and i - K + 1 > flip_inds[flip_pos]:
                flip_pos += 1
            
            is_flipped = False
            if (len(flip_inds) - flip_pos) % 2 != 0:
                is_flipped = True
                
            cur_bit = A[i]
            if is_flipped:
                cur_bit = not cur_bit
            
            if i > len(A) - K:
                if cur_bit == 0:
                    return -1
            else:
                if not cur_bit:
                    flip_inds.append(i)
                
        return len(flip_inds)

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        flipped = [False] * len(A)
        count = [0] * len(A)
        flips = 0
        
        for i in range(len(A)):
            if i > 0:
                x = flipped[i - K] if i >= K else 0
                count[i] = count[i - 1] - x
            
            if (A[i] + count[i]) % 2 == 0:
                count[i] += 1
                flipped[i] = True
                flips += 1

        return flips if not any(flipped[len(A) - K + 1:]) else -1

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        
        Fliped = [0]*len(A)
        cnt = 0
        for i in range(len(A)):
            if i >=K:
                fliped = cnt - Fliped[i-K]
            else:
                fliped = cnt
                
            if (A[i] == 0 and fliped % 2 == 0) or (A[i] == 1 and fliped % 2 == 1):
                if i + K > len(A):
                    return -1                
                A[i] = 1
                cnt += 1
                
            Fliped[i] = cnt
            

                    
        return cnt
                    


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        cur, res, n = 0, 0, len(A)
        for i in range(len(A)):
            if A[i] == (cur % 2):
                if (i + K  > n): return -1 
                res += 1
                cur += 1
                A[i] -= 2
            if (i - K + 1 >= 0) and (A[i-K + 1] < 0):
                cur -= 1
        return res

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        flipped = 0
        status = [0] * len(A)
        flips = 0
        for i in range(len(A)):
            if i >= K:
                flipped ^= status[i - K]
            
            if flipped == A[i]:
                if i + K > len(A):
                    return -1
                flipped ^= 1
                flips += 1
                status[i] = 1
        
        return flips


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        n = len(A)
        num = 0
        flip_queue = []
        flip_sum = 0
        
        for i in range(n-K+1):
            if flip_sum&1:
                add = 1 if A[i] == 1 else 0
            else:
                add = 1 if A[i] == 0 else 0
            num += add
            flip_queue.append(add)  
            flip_sum += add
            if len(flip_queue) >= K:
                flip_sum -= flip_queue.pop(0)
        for j in range(n-K+1, n):
            if flip_sum&1:
                if A[j] == 1:
                    return -1
            else:
                if A[j] == 0:
                    return -1
            flip_queue.append(0)
            if len(flip_queue)>=K:
                flip_sum -= flip_queue.pop(0)
        return num

class Solution:
    
    def minKBitFlips(self, a: List[int], k: int) -> int:
        n = len(a)
        toggles = [0] * (n + 1) # toggles[i] is 1 if we should toggle our view
        min_flips = 0
        view = 0 # 0 means normal, 1 means inverted
        
        for i, b in enumerate(a):
            # If we're ending an interval where we've previously flipped, toggle
            # our view
            view ^= toggles[i]
            if b ^ view == 0: # This value is 0, we've gotta flip it
                if i + k > n: # No way to flip to fix this (can't be done)
                    return -1
                min_flips += 1
                view ^= 1 # toggle our view (view things from now on as flipped)
                toggles[i + k] ^= 1 # toggle our view back once we get to i + k
        return min_flips

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        n = len(A)
        ans = 0
        has_ever_flipped = [0] * n
        valid_flip_count_for_current_idx = 0
        for i in range(n):
            if i >= K:
                if has_ever_flipped[i-K] == 1:
                    valid_flip_count_for_current_idx -= 1
            if valid_flip_count_for_current_idx % 2 == A[i]:
                if i + K > n:
                    return -1
                valid_flip_count_for_current_idx += 1
                has_ever_flipped[i] = 1
                ans += 1
        return ans

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        tot = 0
        flips = []
        mask = 0
        for i in range(len(A) - (K - 1)):
            if flips and i == flips[0]:
                flips.pop(0)
                mask ^= 1
            if A[i] == mask:
                flips.append(i + K)
                tot += 1
                mask ^= 1
        for i in range(len(A) - K, len(A)):
            if flips and i == flips[0]:
                flips.pop(0)
                mask ^= 1
            if A[i] == mask:
                return -1
        return tot


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        N = len(A)
        hint = [0] * N
        ans = 0
        flip = 0
        for i, x in enumerate(A):
            if flip == hint[i]:
                flip = 0
            else:
                flip = 1
            if (x == 1 and flip == 1) or (x == 0 and flip == 0):  # If we must flip the subarray starting here...
                ans += 1  # We're flipping the subarray from A[i] to A[i+K-1]
                if i+K > N:
                    return -1  # If we can't flip the entire subarray, its impossible
                flip = 1-flip
                if i+K < N:
                    hint[i + K] = 1 - hint[i + K]

        return ans
                


class Solution:
    def minKBitFlips(self, A, K):
        cur, res, n = 0, 0, len(A)    # cur is number of flip since start of current window
        for i in range(len(A)):
            if i >= K and A[i - K] > 1:
                A[i - K] -= 2
                cur -= 1
            if cur & 1 ^ A[i] == 0: # first module 2, even flip is no flip, odd flip is one flip
                if i + K > len(A):
                    return -1
                A[i] += 2
                cur += 1
                res += 1
        return res
    
    def minKBitFlips(self, A, K):
        # cur is number of flip since start of current window
        cur = res = 0
        for i in range(len(A)):
            if i >= K and A[i - K] == 2:  # if we flippped at k, that mean from now on, the flip impact is gone. 
                cur -= 1
             # first module 2, even flip is no flip, odd flip is one flip
            if (cur % 2) == A[i]:
                if i + K > len(A):
                    return -1
                A[i] = 2 # mark flipped at i
                cur, res = cur + 1, res + 1
        return res

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        N = len(A)
        hint = [0] * N
        ans = flip = 0

        for i, x in enumerate(A):
            # check if the current index has been marked before
            # if True, then flip the \"flip\" var
            flip ^= hint[i]
            
            if x ^ flip == 0:  # If we must flip the subarray starting here...
                ans += 1  # We're flipping the subarray from A[i] to A[i+K-1]
                
                if i+K > N: 
                    return -1
                
                flip ^= 1
                
                if i+K < N:
                    hint[i+K] = 1

        return ans

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        
        Fliped = [0]*len(A)
        cnt = 0
        for i in range(len(A)):
            if i >=K:
                fliped = cnt - Fliped[i-K]
            else:
                fliped = cnt
                
            if not (( A[i] == 0 ) ^ (fliped % 2 == 0)):
                if i + K > len(A):
                    return -1                
                A[i] = 1
                cnt += 1
                
            Fliped[i] = cnt
            

                    
        return cnt
                    


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        
        count = 0
        stack = collections.deque()
        for i in range(len(A)):
            if stack and i == stack[0]: 
                stack.popleft()
            if A[i] == len(stack)%2:
                if i+ K > len(A): return -1
                count += 1
                stack.append(i+K)

        return count 
        
#         start = count = 0
#         while  start < len(A):
#             if not A[start]:
#                 if start + K > len(A): return -1
#                 for i in range(start, start+K):
#                     A[i] = 1 - A[i]
#                 count += 1
#             start += 1
#         return count
            


class Solution:
    def minKBitFlips(self, A: 'List[int]', K: 'int') -> 'int':
        idx = 0
        num_digits = len(A)
        A_bitrep = int('1' + ''.join([str(i) for i in A]), 2)

        K_bitrep = 2 ** K - 1
        num_flips = 0
        while A_bitrep > K_bitrep:
            if A_bitrep & 1 == 0:
                num_flips += 1
                A_bitrep ^= K_bitrep
            A_bitrep >>= 1

        return num_flips if A_bitrep == K_bitrep else -1


class Solution(object):
    def minKBitFlips(self, A, K):
        N=len(A)
        flip=0
        flip_ends=[0]*(N+1)
        res=0
        
        for i,num in enumerate(A):
            flip^=flip_ends[i]
            if not num^flip:
                if i+K>N:
                    return -1
                else:
                    res+=1
                    flip^=1
                    flip_ends[i+K]=1
                
            
        return res
            
      
        
       


class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        import numpy as np
        Anp = np.array(A).astype(bool)
        idx = 0
        cnt = 0
        while idx < Anp.shape[0]-(K-1):
            if Anp[idx]:
                idx += 1
            else:
                cnt +=1
                Anp[idx:idx+K] = ~Anp[idx:idx+K]
                idx += 1
        if np.sum(Anp[Anp.shape[0]-K:]) != K:
            return -1
        else:
            return cnt

class Solution:
    def minKBitFlips(self, A: List[int], k: int) -> int:
        
        latest_possible_flip = len(A) - k
        flipped = collections.deque()
        flips = 0
        for i in range(len(A)):
            
            if flipped and (flipped[0] < i):
                flipped.popleft()
                
            if len(flipped)&1 == A[i]:
                if i <= latest_possible_flip:
                    flips += 1
                    flipped.append(i+k-1)
                else:
                    return -1
        
        return flips