LeetCode 995. Minimum Number of K Consecutive Bit Flips

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minKBitFlips(vector<int>& A, int K) {
        int n = A.size(), flipped = 0, ans = 0;
        vector<int> isFlipped(n);
        for (int i = 0; i < n; ++i) {
            if (i >= K)
                flipped ^= isFlipped[i - K];
            if (flipped == A[i]) {
                if (i + K > n)
                    return -1;
                isFlipped[i] = 1;
                flipped ^= 1;
                ++ans;
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int minKBitFlips(vector<int>& A, int K) {
        int n = A.size(), flipped = 0, ans = 0;
        queue<int> isFlipped;
        for (int i = 0; i < n; ++i) {
            if (i >= K) {
                flipped ^= isFlipped.front();
                isFlipped.pop();
            }
            if (flipped == A[i]) {
                if (i + K > n)
                    return -1;
                isFlipped.push(1);
                flipped ^= 1;
                ++ans;
            } else {
                isFlipped.push(0);
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minKBitFlips(vector<int>& A, int K) {
        // "cur" is the count of flipping times within current sliding window.
        int n = A.size(), cur = 0, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i >= K && A[i - K] > 1) {
                --cur;
                A[i - K] += 2;
            }
            if (cur % 2 == A[i]) {
                if (i + K > n)
                    return -1;
                A[i] += 2;
                ++cur;
                ++ans;
            }
        }
        return ans;
    }
};

Reference: [Java/C++/Python] One Pass and O(1) Space - LeetCode Discuss.