Light Every Lamp With a Window

Hard

A string of lamps is described by the array bits: 1 means the lamp is on, 0 means it is off. The remote can do one thing: pick width **consecutive** lamps and toggle each of them (on becomes off, off becomes on). Return the smallest number of presses that leaves every lamp on, or -1 if that is impossible.

Example 1

bits=[0, 0, 1, 0, 0, 1], width=3 → 2

Toggle window 0–2: [1, 1, 0, 0, 0, 1], then window 2–4: [1, 1, 1, 1, 1, 1].

Example 2

bits=[1, 0, 1], width=2 → -1

The 0 at position 1 can only be fixed by window 1–2, but that turns off the last lamp, and there is no window further right.

Example 3

bits=[0, 0], width=1 → 2

Constraints

1 ≤ len(bits) ≤ 10⁵
bits[i] is 0 or 1
1 ≤ width ≤ len(bits)

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Queue Array Prefix Sum Sliding Window

Similar problems

Three-Lamp Switch Medium Shortest Stretch Reaching a Total Hard Longest Affordable Run of Machines Hard Signal in the Remotest Village Hard Moving Window Maximum Hard

Input

bits=[0, 0, 1, 0, 0, 1], width=3

Expected

Run checks the first 3 tests in your browser. Submit checks all 103 tests on the server, hidden ones included.