Minimum Number of K Consecutive Bit Flips

hard bit manipulation greedy difference array

Problem

You are given a binary array nums and an integer k. A k-bit flip chooses a contiguous subarray of length exactly k and flips every bit in it (0 becomes 1, 1 becomes 0). Return the minimum number of k-bit flips needed to make the array contain no 0s. If it is not possible, return -1.

Inputnums = [0, 0, 0, 1, 0, 1, 1, 0], k = 3

Output3

Flip at index 0 → [1,1,1,1,0,1,1,0], flip at index 4 → [1,1,1,1,1,0,0,0], flip at index 5 → [1,1,1,1,1,1,1,1].

nums (comma-separated 0/1)

def min_k_bit_flips(nums, k):
    n = len(nums)
    diff = [0] * (n + 1)
    flipped = 0
    ans = 0
    for i in range(n):
        flipped += diff[i]
        if (nums[i] + flipped) % 2 == 0:
            if i + k > n:
                return -1
            ans += 1
            flipped += 1
            diff[i + k] -= 1
    return ans

function minKBitFlips(nums, k) {
  const n = nums.length;
  const diff = new Array(n + 1).fill(0);
  let flipped = 0, ans = 0;
  for (let i = 0; i < n; i++) {
    flipped += diff[i];
    if ((nums[i] + flipped) % 2 === 0) {
      if (i + k > n) return -1;
      ans++;
      flipped++;
      diff[i + k]--;
    }
  }
  return ans;
}

class Solution {
    public int minKBitFlips(int[] nums, int k) {
        int n = nums.length;
        int[] diff = new int[n + 1];
        int flipped = 0, ans = 0;
        for (int i = 0; i < n; i++) {
            flipped += diff[i];
            if ((nums[i] + flipped) % 2 == 0) {
                if (i + k > n) return -1;
                ans++;
                flipped++;
                diff[i + k]--;
            }
        }
        return ans;
    }
}

int minKBitFlips(vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> diff(n + 1, 0);
    int flipped = 0, ans = 0;
    for (int i = 0; i < n; i++) {
        flipped += diff[i];
        if ((nums[i] + flipped) % 2 == 0) {
            if (i + k > n) return -1;
            ans++;
            flipped++;
            diff[i + k]--;
        }
    }
    return ans;
}

Explanation

We sweep left to right and use a simple rule: if the current position still shows a 0 after accounting for earlier flips, we are forced to start a flip here, because nothing to the right can fix this leftmost zero. This greedy choice is always optimal.

The challenge is that a length-k flip affects k cells, and flips overlap. Instead of actually flipping ranges (which would be slow), we track how many flips currently cover the position with a counter flipped, and use a difference array diff to know when a flip stops affecting later cells.

At index i we add diff[i] into flipped. The real bit is (nums[i] + flipped) % 2: an even total means the original bit survives, odd means it got toggled. If that effective bit is 0, we must flip starting here: increment ans, bump flipped, and schedule the flip to expire at i + k by doing diff[i + k] -= 1. If a needed flip would run past the end (i + k > n), it is impossible, so return -1.

Example: nums = [0,0,0,1,0,1,1,0], k = 3. Index 0 is 0 → flip [0..2]; index 4 becomes effectively 0 → flip [4..6]; index 5 is then 0 → flip [5..7]. That is 3 flips, and every cell ends as 1.

The difference array makes each flip's expiry a single update, so the whole sweep runs in one linear pass.

Time: O(n) Space: O(n)