Flip Switches in Fixed Blocks
HardGreedy
Problem
A panel has a row of switches; switches[i] is 1 if switch i is on and 0 if off. A lever toggles exactly width consecutive switches at once (every on becomes off and vice versa).
Return the minimum number of lever pulls needed to turn every switch on, or -1 if it cannot be done.
Example 1
- Input:
- switches = [0, 1, 0], width = 1
- Output:
- 2
Toggle switch 0 and switch 2 individually.
Example 2
- Input:
- switches = [1, 1, 0], width = 2
- Output:
- -1
Toggling [0..1] or [1..2] always leaves a switch off.
Example 3
- Input:
- switches = [0, 0, 1, 0, 1, 1, 1, 0], width = 3
- Output:
- 4
Toggle the blocks starting at 0, 2, 4 and 5.
Constraints
- 1 ≤ switches.length ≤ 10^5
- 1 ≤ width ≤ switches.length
- switches[i] is 0 or 1
Hint
Show the first hint
Does the order of pulls matter? Does pulling the same block twice ever help?
Walkthrough
How to approach it
01Clarify before coding
- Can blocks overlap? Yes.
- Does the order of pulls matter? No: each switch's final state depends only on how many blocks cover it (parity).
- What if it is impossible? Return −1.
02Brute force
Since order does not matter and repeating a block cancels out, try every subset of block starts.
Cost: O(2^(n − width + 1) · n). Even simulating the greedy naively (actually toggling width switches per pull) is O(n · width) = 10^10 in the worst case.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.