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]
 

Note:

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

Solution:

class Solution {
    public int minKBitFlips(int[] A, int K) {
        int n = A.length, flip = 0;
        for (int i = 0; i < n; i ++) {
            if (A[i] == 1) continue;
            if (i + K > n) return -1;
            for (int j = i; j < i + K; j ++) {
                A[j] = 1 - A[j];
            }
            flip ++;
        }
        return flip;
    }
}


Intuition:


There is only one way to filp A[0],
and A[0] will tell us if we need to filp the range A[0] ~ A[K -1].
So we start from the leftmost one by one using a greedy idea to solve this problem.


Solution 1


Explanation
Create a new array isFlipped[n].
isFlipped[i] = 1 iff we flip K consecutive bits starting at A[i].


We maintain a variable flipped and flipped = 1 iff the current bit is flipped.


If flipped = 0 and A[i] = 0, we need to flip at A[i].
If flipped = 1 and A[i] = 1, we need to flip at A[i].

In a word, we compare the flipped status of current index's left neighbor with i - k to determine if current index i appears flipped or not.
Now suppose we are traversing the array from the very beginning, and flipped represents if the position current being examined APPEARS flipped or not.
Our current index pointer is i.
Then, when we are at this line (before execution of this line), flipped is still the status of last iteration, which means the flipping status of current position's left neighbor.
So, between index i-k + 1 (that is, after we process the index i - k ) and i-1, there might be unknown number of flipping operations.
We do not need to know the exact number, we just need to know if it is even or odd number of times, since all these operations in between would affect current position i.
if flipped from last iteration is same as isFlipped[i - k], it means we did even number of flipping in between, which would also make the number at index i APPEAR unaffected.

Complexity
O(N) time for one pass
O(N) extra space for isFlipped[n].


Java


    public int minKBitFlips(int[] A, int K) {
        int n = A.length, flipped = 0, res = 0;
        int[] isFlipped = new int[n];
        for (int i = 0; i < A.length; ++i) {
            if (i >= K)
                flipped ^= isFlipped[i - K];
            if (flipped == A[i]) {
                if (i + K > A.length)
                    return -1;
                isFlipped[i] = 1;
                flipped ^= 1;
                res++;
            }
        }
        return res;
    }