#995
Minimum Number of K Consecutive Bit Flips
expert · 1130 · lc hard +32 · verified · 62.3% accepted · 2,055 likes · top 63%
Description
You are given a binary array nums and an integer k.
A k-bit flip selects a contiguous subarray of length k and inverts every bit in it (0 becomes 1 and 1 becomes 0).
Return the minimum number of k-bit flips needed so that nums contains no 0s. If it is impossible, return -1.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [0,1,0], k = 1
Output: 2
Explanation: Flip nums[0], then flip nums[2].
Example 2:
Input: nums = [1,1,0], k = 2
Output: -1
Explanation: No matter how we flip subarrays of size 2, we cannot make the array become [1,1,1].
Example 3:
Input: nums = [0,0,0,1,0,1,1,0], k = 3
Output: 3
Explanation:
Flip nums[0],nums[1],nums[2]: nums becomes [1,1,1,1,0,1,1,0]
Flip nums[4],nums[5],nums[6]: nums becomes [1,1,1,1,1,0,0,0]
Flip nums[5],nums[6],nums[7]: nums becomes [1,1,1,1,1,1,1,1]
Code
1
2
3