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

Source: leetcode | Difficulty: MEDIUM
Tags: Bit manipulation

Data structures

Amortized analysis

Range queries

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)):
			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
			elif 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


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:
		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
			elif 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:
		flipped = collections.deque()
		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
		counter = 0
		flip = 0
		for (i, x) in enumerate(A):
			flip = (flip + hint[i]) % 2
			if x == 1 and flip == 1 or (x == 0 and flip == 0):
				counter += 1
				if i + K > N:
					return -1
				flip = 1 - flip
				if i + K < N:
					hint[i + K] = 1
		return counter


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:
		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)
		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:
		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)
			elif 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:
		counter = 0
		q = []
		qL = 0
		for i in range(len(A) - K + 1):
			if A[i] == (len(q) - qL) % 2:
				counter += 1
				q.append(i + K - 1)
			if qL < len(q) and q[qL] == i:
				qL += 1
		for i in range(len(A) - K + 1, len(A)):
			if A[i] == (len(q) - qL) % 2:
				return -1
			if qL < len(q) and q[qL] == i:
				qL += 1
		return counter


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]
			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:
		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:
				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:
					return -1
				else:
					maxFlipCnt += 1
					effectiveFlipCnt += 1
					reduceInds.append(i + K)
		return maxFlipCnt


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:
		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:
		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:
		(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)]
		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
		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)
		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:
				return -1
			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:
			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:
		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:

	def minKBitFlips(self, A: List[int], K: int) -> int:
		start = 0
		count = 0
		res = 0
		for (end, a) in enumerate(A):
			if count ^ A[end] == 0:
				A[end] -= 2
				res += 1
				count ^= 1
			if end >= start + K - 1:
				if A[start] < 0:
					count ^= 1
					A[start] += 2
				start += 1
		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)
				elif 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:
		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:
		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:
		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:
		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 i + K - 1 <= len(A) - 1:
					ans += 1
					win.append(i)
				else:
					return -1
		return ans


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, 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:
		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 flips != [] and flips[-1] + K - 1 >= ALen:
			return -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 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:
		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
			elif 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)
		min_flips = 0
		view = 0
		for (i, b) in enumerate(a):
			view ^= toggles[i]
			if b ^ view == 0:
				if i + k > n:
					return -1
				min_flips += 1
				view ^= 1
				toggles[i + k] ^= 1
		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':
		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