Solution
Approach 1: Simulation
Intuition
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 t
.
Algorithm
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.
Complexity Analysis

Time Complexity: , where is the number of cells in the prison.

Space Complexity: .
Analysis written by: @awice.