Approach 1: Simulation
We simulate each day of the prison.
Because there are at most 256 possible states for the prison, eventually the states repeat into a cycle rather quickly. We can keep track of when the states repeat to find the period
t of this cycle, and skip days in multiples of
Let's do a naive simulation, iterating one day at a time. For each day, we will decrement
N, the number of days remaining, and transform the state of the prison forward (
state -> nextDay(state)).
If we reach a state we have seen before, we know how many days ago it occurred, say
t. Then, because of this cycle, we can do
N %= t. This ensures that our algorithm only needs steps.
Time Complexity: , where is the number of cells in the prison.
Space Complexity: .
Analysis written by: @awice.