First, we note that toggle operations are commutative so Wesley has the ability to "accumulate" switch usages, such that instead of using one switch per second for the first ~i~ seconds, he can simply perform ~i~ switch usages during the ~i^\text{th}~ second. We then notice that it will take at most ~N~ seconds to flip all the switches off, since at most ~N~ lights will be on by the ~N^\text{th}~ second and Wesley will accumulate up to ~N~ switch usages by then.

Subtask 1

For the first subtask, we keep track of the state of each light throughout the first ~M~ seconds, and after the ~i^\text{th}~ second we check if there are at most ~i~ lights turned on by iterating through our array storing the lights' states. Be aware that the answer could be greater than ~M~.

Time Complexity: ~\mathcal{O}(N \cdot M)~

Subtask 2

Instead of iterating through the array storing lights' states, we can use a counter to keep track of how many lights are on at any given moment. We no longer need to recount the number of lights turned on at every iteration.

Time Complexity: ~\mathcal{O}(N + M)~