-
Notifications
You must be signed in to change notification settings - Fork 0
LC 0995 [H] Minimum Number of K Consecutive Bit Flips
Code with Senpai edited this page Jul 10, 2022
·
1 revision
'''
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
footer