569. Prison Cells After N Days
A corridor holds exactly 8 prison cells in a row. Each cell is either occupied (1) or vacant (0).
Every night, all cells update simultaneously by one rule: a cell is occupied the next morning exactly when the two cells beside it were both occupied or both vacant the previous day; otherwise it becomes vacant. The first and last cells have only one neighbor, so after any night they are always vacant.
You receive cells, an array of 8 zeros and ones describing the corridor today, and an integer n. Return an array of 8 zeros and ones describing the corridor after n nights have passed.
n can be as large as a billion — a day-by-day loop is too slow at the top end, so think about how many distinct corridor states can even exist.
Example 1:
Input: cells = [0, 1, 0, 1, 1, 0, 0, 1], n = 7
Output: [0, 0, 1, 1, 0, 0, 0, 0]
Explanation: Applying the neighbor rule seven times in a row transforms the corridor step by step; after the seventh night the occupied cells are positions 2 and 3.
Example 2:
Input: cells = [1, 0, 0, 1, 0, 0, 1, 0], n = 1
Output: [0, 0, 0, 1, 0, 0, 1, 0]
Explanation: One night: cell 3 keeps company on both sides equal (cells 2 and 4 are both 0), cell 6 likewise (cells 5 and 7 are both 0); the ends go vacant.
Constraints:
- cells.length == 8
- cells[i] is 0 or 1
- 1 ≤ n ≤ 10⁹
Hints:
There are only 2^8 = 256 possible corridors — and after the first night both ends are 0, leaving at most 64 reachable states. A billion steps cannot all be new.
Simulate one day at a time, but remember each state you have seen (a tuple or an 8-bit integer) together with the day you saw it. The first repeat reveals the cycle length.
Once you know the cycle length L, the answer after n days equals the answer after the remaining (n − day) mod L extra steps — fast-forward instead of looping.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: cells = [0, 1, 0, 1, 1, 0, 0, 1], n = 7
Expected output: [0, 0, 1, 1, 0, 0, 0, 0]