hardGreedyPure DSA~45 min
Minimum K-Length Flips to Clear All Zeros
A bit array must become all ones. Each operation flips a contiguous block of exactly k bits. Find the fewest flips, or report it is impossible.
Problem
Given a binary array nums and an integer k, in one move you choose a contiguous subarray of length exactly k and flip every bit (0↔1). Return the minimum number of moves to make every element 1, or -1 if it cannot be done.
Input
A binary array nums and an integer k.
Output
An integer: the minimum number of k-length flips, or -1.
Constraints
- 1 <= k <= nums.length <= 10^5
- nums[i] is 0 or 1.
Examples
Example 1
Input
nums = [0,1,0], k = 1
Output
2
Flip index 0 and index 2 individually.
Example 2
Input
nums = [1,1,0], k = 2
Output
-1
No length-2 flip can fix index 2 without breaking earlier bits.