Show problems as
Classic problem #995HardArrayBit ManipulationQueueSliding WindowPrefix SumBrute-Force Search

Minimum Number of K Consecutive Bit Flips

Real-world version: Flipping Windows to Raise Every Switch
Tracked in this browser only
Read Minimum Number of K Consecutive Bit Flips on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A row of switches holds only 0 and 1. One move picks exactly k neighbouring switches and flips every one of them, so each 0 becomes a 1 and each 1 becomes a 0.

Return the fewest moves that leave every switch showing 1, or -1 when no number of moves can do it.

Examples

Example 1

Input
switches = [0, 0, 0, 0], k = 2
Output
2

Flip the first two switches and then the last two.

Example 2

Input
switches = [0, 1], k = 2
Output
-1

Only one window exists and it covers both switches, so flipping it turns the 1 off while turning the 0 on, and the row can never come out all ones.

Example 3

Input
switches = [1, 0, 1, 0, 1, 0, 1], k = 1
Output
3

A window of one switch flips a single switch, so each of the three zeros costs its own move.

Constraints

  • 1 <= k <= switches.length <= 10^5
  • 0 <= switches[i] <= 1

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def min_k_bit_flips(switches: list[int], k: int) -> int:
Java
public int minKBitFlips(int[] switches, int k)

More on the same topics