# 995. Minimum Number of K Consecutive Bit Flips

## Problem setting¶

This problem "Minimum Number of K Consecutive Bit Flips" is one of the hard problems in LeetCode weekly contest 124. I was not able to spend the time during the contest. So let me review the solution line by line.

Given an array A of non-negative integers, the array is squareful if for every pair of adjacent elements, their sum is a perfect square.

Return the number of permutations of A that are squareful. Two permutations A1 and A2 differ if and only if there is some index i such that A1[i] != A2[i].

Note: 1 <= A.length <= 30000 1 <= K <= A.length

### 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]

## Solution from Huoran Li¶

In [3]:
import collections

class Solution:
def minKBitFlips(self, A: 'List[int]', K: 'int') -> 'int':
a = A
n = len(a)
k = K

ans = 0
cnt = 0
mark = collections.deque()
for i in range(n - k + 1):
while cnt > 0 and i - mark[0] >= k:
cnt -= 1
mark.popleft()

if cnt % 2 == 0:
if a[i] == 0:
cnt += 1
ans += 1
mark.append(i)
a[i] = 1
else:
pass
else:
if a[i] == 0:
a[i] = 1
pass
else:
cnt += 1
ans += 1
mark.append(i)
# print(i, a, mark)

for i in range(n - k + 1, n):
while cnt > 0 and i - mark[0] >= k:
cnt -= 1
mark.popleft()

if cnt % 2 == 0 and a[i] == 0:
return -1
if cnt % 2 == 1 and a[i] == 1:
return -1
return ans


## Step-by-step understanding¶

Overall solution:

1. Iterate over the array to find 0
2. Flip a K subarray unless Kth element is not beyond the array A
3. Back to 1 and continue.

### Deque¶

One of the key data type used in this solution is called deque from collection module. Let's see the example how to use deque.

Deque is a list-like object but suitable for fast appends and pops.

#### Deque vs List Comparison¶

As you can see below, deque and list has quite similar usage. reference: https://pymotw.com/2/collections/deque.html

In [15]:
import collections

d = collections.deque('abcdefg')

print('=== Deque ===')
print(f'Deque: {d}')
print(f'Length: {len(d)}' )
print(f'Left end: {d[0]}')
print(f'Right end: {d[-1]}')

d.remove('c')
print(f'remove(c): {d}')

=== Deque ===
Deque: deque(['a', 'b', 'c', 'd', 'e', 'f', 'g'])
Length: 7
Left end: a
Right end: g
remove(c): deque(['a', 'b', 'd', 'e', 'f', 'g'])

In [16]:
print('=== List ===')
l = list('abcdefg')

print(f'List: {l}')
print(f'Length: {len(l)}' )
print(f'Left end: {l[0]}')
print(f'Right end: {l[-1]}')
l.remove('c')
print(f'remove(c): {l}')

=== List ===
List: ['a', 'b', 'c', 'd', 'e', 'f', 'g']
Length: 7
Left end: a
Right end: g
remove(c): ['a', 'b', 'd', 'e', 'f', 'g']


#### deque.popleft¶

deque.popleft removes and returns the leftmost element. The same function of pop but affect from left side, not right.

### First for Loop¶

n is the length of an given array A, and k is the maximum number of the length of a sub array that we can flip.

In [ ]:
for i in range(n - k + 1):
while cnt > 0 and i - mark[0] >= k:
cnt -= 1
mark.popleft()

if cnt % 2 == 0:
if a[i] == 0:
cnt += 1
ans += 1
mark.append(i)
a[i] = 1
else:
pass
else:
if a[i] == 0:
a[i] = 1
pass
else:
cnt += 1
ans += 1
mark.append(i)
# print(i, a, mark)


For example 3,

In [52]:
A = [0,0,0,1,0,1,1,0]
n = len(A)
K = 3


i will be ranged around:

In [53]:
f'{[i for i in range(n - K + 1)]}'

Out[53]:
'[0, 1, 2, 3, 4, 5]'
In [54]:
k = 3
a = A
cnt = 0
ans = 0
mark = collections.deque()

for i in range(n - k + 1):
print(f'i: {i}\ncnt: {cnt}\nans: {ans}')
print(f'deque: {mark}')
print(f'A: {a}')
print()

while cnt > 0 and i - mark[0] >= k:
cnt -= 1
mark.popleft()

# When counter is even number
if cnt % 2 == 0:
if a[i] == 0:
cnt += 1
ans += 1
mark.append(i)
a[i] = 1
else:
pass
# When counter is odd number
else:
if a[i] == 0:
a[i] = 1
pass
else:
cnt += 1
ans += 1
mark.append(i)

i: 0
cnt: 0
ans: 0
deque: deque([])
A: [0, 0, 0, 1, 0, 1, 1, 0]

i: 1
cnt: 1
ans: 1
deque: deque([0])
A: [1, 0, 0, 1, 0, 1, 1, 0]

i: 2
cnt: 1
ans: 1
deque: deque([0])
A: [1, 1, 0, 1, 0, 1, 1, 0]

i: 3
cnt: 1
ans: 1
deque: deque([0])
A: [1, 1, 1, 1, 0, 1, 1, 0]

i: 4
cnt: 0
ans: 1
deque: deque([])
A: [1, 1, 1, 1, 0, 1, 1, 0]

i: 5
cnt: 1
ans: 2
deque: deque([4])
A: [1, 1, 1, 1, 1, 1, 1, 0]



### Second for loop¶

for i in range(n - k + 1, n):
while cnt > 0 and i - mark[0] >= k:
cnt -= 1
mark.popleft()

if cnt % 2 == 0 and a[i] == 0:
return -1
if cnt % 2 == 1 and a[i] == 1:
return -1
return ans

In [48]:
f'{[i for i in range(n - K + 1, n)]}'

Out[48]:
'[6, 7]'
In [55]:
# Second For Loop
for i in range(n - k + 1, n):
print(f'i: {i}\ncnt: {cnt}\nans: {ans}')
print(f'deque: {mark}')
print(f'A: {a}')
print()

while cnt > 0 and i - mark[0] >= k:
cnt -= 1
mark.popleft()

if cnt % 2 == 0 and a[i] == 0:
#         return -1
print('return: -1')
if cnt % 2 == 1 and a[i] == 1:
print('return: -1')
#         return -1
print(f'return: {ans}')
# return ans

i: 6
cnt: 2
ans: 3
deque: deque([4, 5])
A: [1, 1, 1, 1, 1, 1, 1, 0]

i: 7
cnt: 2
ans: 3
deque: deque([4, 5])
A: [1, 1, 1, 1, 1, 1, 1, 0]

return: 3