# 995. 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

• 当 curFlipped 为0，表示没有翻转，且原数组 A[i] 为0，此时就需要翻转i位置。

• 当 curFlipped 为1，表示翻转过了，而原数组 A[i] 为1，表示虽然原来是1，但是当前位置受之前翻转的影响变成了0，此时就需要翻转回来。

class Solution {
public:
int minKBitFlips(vector<int>& A, int K) {
int res = 0, n = A.size(), curFlipped = 0;
vector<int> isFlipped(n);
for (int i = 0; i < n; ++i) {
if (i >= K) curFlipped ^= isFlipped[i - K];
if (curFlipped % 2 == A[i]) {
if (i + K > n) return -1;
isFlipped[i] = 1;
curFlipped ^= 1;
++res;
}
}
return res;
}
};

class Solution {
public:
int minKBitFlips(vector<int>& A, int K) {
int res = 0, n = A.size();
queue<int> q;
for (int i = 0; i < n; ++i) {
if (!q.empty() && i >= (q.front() + K)) q.pop();
if (q.size() % 2 == A[i]) {
if (i + K > n) return -1;
q.push(i);
++res;
}
}
return res;
}
};

class Solution {
public:
int minKBitFlips(vector<int>& A, int K) {
int res = 0, n = A.size(), flipped = 0;
for (int i = 0; i < n; ++i) {
if (i >= K) flipped -= A[i - K] / 2;
if (flipped % 2 == A[i]) {
if (i + K > n) return -1;
A[i] += 2;
++flipped;
++res;
}
}
return res;
}
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/995

Bulb Switcher

https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/

https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/discuss/239284/C%2B%2B-greedy-stack-and-O(1)-memory

https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/discuss/239117/Java-O(n)-Sliding-Window-Solution-using-Queue

https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/discuss/238609/JavaC%2B%2BPython-One-Pass-and-O(1)-Space

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation