Three-Lamp Switch

Medium

A row of lamps is given as the array lamps: 1 means the lamp is on, 0 means it is off. A switch toggles three neighbouring lamps at once: the ones that were on go off and the ones that were off come on. You may use it any number of times, on any three consecutive lamps. Return the minimum number of presses that leaves every lamp on, or -1 if the whole row can never be lit.

Example 1

lamps=[1, 0, 0, 0, 1] → 1

One press on lamps 1–3 and the whole row is lit.

Example 2

lamps=[0, 0, 1, 1, 0, 1] → -1

Press 0–2: [1, 1, 0, 1, 0, 1]. Then 2–4: [1, 1, 1, 0, 1, 1]. Then 3–5: all lit. 3 presses in total.

Example 3

lamps=[1, 1, 0, 1] → -1

Lamp 0 is only toggled by the triple 0–2, so that triple is pressed an even number of times. Lamp 1 is toggled by 0–2 and 1–3, so 1–3 is pressed an even number of times as well. Then lamp 2 ends up unchanged and stays off.

Constraints

3 ≤ len(lamps) ≤ 10⁵
lamps[i] is 0 or 1

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

Light Every Lamp With a Window Hard Shortest Stretch Reaching a Total Hard Longest Affordable Run of Machines Hard Signal in the Remotest Village Hard Shortest Stretch to the Goal Medium

Input

lamps=[1, 0, 0, 0, 1]

Expected

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