You are standing in front of a hallway with N consecutive doors. You want to cross through the N doors.
You may only walk through open doors. You also have a magic wand, that can flip the state of all doors. Determine the minimum number of times you need to use the wand.
The solution is rather straightforward.
If the door we have to cross is open, simply walk through it (it makes no sense to use the wand and close the door) and if the door is closed, use the wand, flipping the status of all doors, and then walk through the door.
All that remains is to implement the above idea efficiently. Everytime we use the wand, it is inefficient to manually flip the status of all doors.
Rather, if we have used the wand k times thus far, the status of any door is equal to its initial state if k is even, and is flipped otherwise (the proof of which is trivial and left to the reader as an exercise).
Therefore, we iterate through the doors from left to right, and in each step, check if the door is open or closed (with the above trick) and use the wand appropriately.
Since we iterate through the N doors once, the total time complexity is
per test case.
Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)