LC 0995 [H] Minimum Number of K Consecutive Bit Flips - ALawliet/algorithms GitHub Wiki

'''
Solution 3
Explanation:
One pass.
cur means the number of flips in the current sliding window of size K.
If cur is even and A[i] is 0, we need to flip.
If cur is odd and A[i] is 1, we need to flip.

If we want to flip A[i], we add 2 to it.
The flipped 0 is 2 and flipped 1 is 3 now.
When they go out of the window, we will change them back.
So no worries if we change the input.

Complexity:
O(N) time for one pass
O(1) extra space.
'''
class Solution:
    # def minKBitFlips(self, nums: List[int], k: int) -> int:
    def minKBitFlips(self, A, K):
        cur, res, n = 0, 0, len(A)
        for i in range(len(A)):
            if i >= K and A[i - K] > 1:
                A[i - K] -= 2
                cur -= 1
            if cur & 1 ^ A[i] == 0:
                if i + K > len(A):
                    return -1
                A[i] += 2
                cur += 1
                res += 1
        return res
    
    def minKBitFlips(self, a: 'List[int]', k: 'int') -> 'int':
        q = deque()
        res = 0
        for i in range(len(a)):
            if len(q) % 2 != 0:
                if a[i] == 1:
                    res += 1
                    q.append(i+k-1)
            else:
                if a[i] == 0:
                    res += 1
                    q.append(i+k-1)
            if q and q[0] == i: q.popleft()
            if q and q[-1] >= len(a): return -1
        return res
    
    def minKBitFlips(self, a: 'List[int]', k: 'int') -> 'int':
        res = 0
        flips = 0
        addon = 10
        for i in range(len(a)):
            if flips % 2 != 0:
                if (a[i] - addon) % 2 == 1:
                    res += 1
                    if i+k-1 >= len(a): return -1
                    a[i+k-1] += addon
                    flips += 1
            else:
                if (a[i] - addon) % 2 == 0:
                    res += 1
                    if i+k-1 >= len(a): return -1
                    a[i+k-1] += addon
                    flips += 1
            if a[i] > 1: 
                flips -= 1
                a[i] -= addon #Restore the array value back
        return res
    
    def minKBitFlips(self, a: 'List[int]', k: 'int') -> 'int':
        res = 0
        flips = 0
        addon = 10
        for i in range(len(a)):
            if (flips % 2 != 0 and (a[i] - addon) % 2 == 1) or (flips % 2 == 0 and (a[i] - addon) % 2 == 0):
                    res += 1
                    if i+k-1 >= len(a): return -1
                    a[i+k-1] += addon
                    flips += 1
            if a[i] > 1: 
                flips -= 1
                a[i] -= addon
        return res