Q995: Minimum Number of K Consecutive Bit Flips
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]
The solution suggests to do it greedily.
By “greedy”, it means that we could start from the very left and if there is 0
at position i, we apply K-bit operation for the subarray
A[i], ..., A[i + K - 1].
And then, the solution discusses about how to do this in an efficient way.
For the latter, it utilizes the trick constantly appearing in handling interval.
From my word, we can define an interval by marking up the start and end position.
And we read the interval via scanning the list and at each iteration, we grab
the information from the previous position and the mark of the current position
to know if the current point is in any interval.
OK, the above discussion is very hand-waving in two senses:
- Why the greedy approach works?
- How exactly is it implemented?
First thing first: Why greedy? Note that the only mattering thing is the number of operations on each position. So, if we can see that the order of the operations does not matter. Consider the very left entry, only 0 or 1 operation makes sense, any more operations are not necessary (they cancel out themselves). Then, we can go the next entry and do the same reasoning given that we’ve know that it has been applied 0 or 1 operation from the left. With this reasoning, we can construct the solution starting from the left and determine at each entry if we want to do 1 operation to make it 1.
OK, secondly: How to do it efficiently? It turns out that we only need to scan the list once (so the time complexity is $O(N)$). Note that we only care about whether or not the number of operations at each position is even. So, we can have a pointer telling the even/odd status of the current position where, like the trick in interval, we can get this information from the previous position. So, we can mark the end position of an operation to flag that the status is one operation different from the previous position since the interval ends.
OK, taking together, we can have the following pseudo-code.
input: A (list), K (size of operation)
interval_status = [ 0 for i in A ] + [ 0 ] # one more for convenience.
# XOR ^ does flip by if_flip ^ curr_status:
# 0 ^ 0 = 0, 1 ^ 1 = 0, 0 ^ 1 = 1, 1 ^ 0 = 1.
counter = 0
prev = 0 # record whether to do flip or not
for i in 1 .. len(A) {
# update the flip status for the current position.
prev = prev ^ interval_status[i]
# with such flip, determine the current status of the position.
curr_status = prev ^ A[i]
if curr_status == 0 {
# want to flip.
# but we need to check if we could flip.
if i + K - 1 <= len(A) {
interval_status[i + K] ^= 1
counter += 1
# we do one more flip, so record it.
prev = prev ^ 1
} else {
# cannot flip.
return -1
}
} else {
# don't want to flip
# do nothing
}
}
return counter
The Python submission.
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