# 995.Minimum-Number-of-K-Consecutive-Bit-Flips

## 995. Minimum Number of K Consecutive Bit Flips

## 题目地址

<https://leetcode.com/problems/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]
```

## 代码

### Approach 1: Greedy + Events

Flip ^0 = flip

Flip ^1 = \~flip

```java
class Solution {
  public int minKBitFlips(int[] A, int K) {
        int N = A.length;
    int[] hint = new int[N];
    int ans = 0, flip = 0;

    for (int i = 0; i < N; i++) {
      flip ^= hint[i]; // first 0^0 = 0
      if (A[i] == flip) {
        ans++;
        if (i + K > N) {
          return -1;
        }
        flip ^= 1; // 0^1 = 1, 1^1 = 0
        if (i + K < N) {
          hint[i + K] ^= 1;
        }
      }
    }

    return ans;
  }
}
```

### Approach #2

解法，贪心 证明： 如果第一个是0， 它别无选择，只能带动右边的K-1个一起转奇数次。（因为求最小，我们只转一次） 如果第一个是1， 它别无选择，只能带动右边的K-1个一起转偶数次。（因为求最小， 我们转 0次） 现在第一个搞定了， 下面解决 N - 1的子问题。

但不管怎么样，请不要动前面已经处理好的。万一你动了，你还得动回来，不折腾。

```java
public int minKBitFlips(int[] A, int K) {
    int count = 0;
    for (int i = 0; i < A.length; i++) {
        if (A[i] == 1) continue;
        if (i + K - 1 < A.length) {
            for (int j = 0; j < K; j++) {
                A[i + j] = 1 - A[i + j];
            }
            count++;
        } else {
            return -1;
        }
    }
    return count;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wentao-shao.gitbook.io/leetcode/array/995.minimum-number-of-k-consecutive-bit-flips.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.