Bulbs and Switches
InterviewTime limit2sMemory limit128 MB
Given current and target bulb states, determine the minimum number of switch presses (each flipping a small neighborhood) needed, or -1 if impossible.
- Level
Medium5 of 10
- Topics
- Greedy, Simulation, Array
- Solved
- No attempts yet
Problem
There are N switches and N bulbs arranged in a row. Each bulb is either on or off.
For 2 <= i <= N - 1, pressing switch i flips the states of bulbs i - 1, i, and i + 1. An on bulb becomes off, and an off bulb becomes on. Pressing switch 1 flips bulbs 1 and 2. Pressing switch N flips bulbs N - 1 and N.
Given the current states of all bulbs and the target states, write a program that finds the minimum number of switch presses needed to reach the target.
Input
The first line contains an integer N (2 <= N <= 100,000).
The second line contains a length-N string representing the current bulb states. The third line contains a length-N string representing the target bulb states. In both strings, 0 means on and 1 means off.
Output
Print the minimum number of switch presses. If the target state cannot be made, print -1.