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, then flip A.


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,A,A: A becomes [1,1,1,1,0,1,1,0]
Flip A,A,A: A becomes [1,1,1,1,1,0,0,0]
Flip A,A,A: A becomes [1,1,1,1,1,1,1,1]


Note:

1. 1 <= A.length <= 30000
2. 1 <= K <= A.length

## Solution: Greedy

From left most, if there is a 0, that bit must be flipped since the right ones won’t affect left ones.

Time complexity: O(nk) -> O(k)
Space complexity: O(1)

## C++ / O(n)

If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website ## Be First to Comment

Mission News Theme by Compete Themes.