Prison Cells After N Days
Medium · Arrays & Hashing · Array · Hash Table · Math · Bit Manipulation · Simulation
Problem
A row of 8 prison cells is either occupied (1) or vacant (0). Every day the whole row changes at once:
- If a cell's two neighbors are both occupied or both vacant, the cell becomes occupied.
- Otherwise, it becomes vacant.
The first and last cells have only one neighbor, so they are always vacant from day 1 on.
You are given the starting row cells and an integer n. Return the row after n days. n can be as large as 10^9, so simulating every day is not an option.
Examples
Input: cells = [1,0,0,1,0,0,1,0], n = 1 Output: [0,0,0,1,0,0,1,0]
Cells 3 and 6 have two vacant neighbors, so only they are occupied the next day; the ends are vacant.
Input: cells = [0,1,1,0,1,0,0,1], n = 1000000000 Output: [0,1,1,1,1,1,1,0]
From day 1 on the rows repeat every 14 days, so day 10^9 looks like day (10^9 - 1) % 14 + 1 = 6.
Input: cells = [0,1,0,1,1,0,0,1], n = 7 Output: [0,0,1,1,0,0,0,0]
Seven daily updates of the rule.
Constraints
- len(cells) == 8
- cells[i] is 0 or 1
- 1 <= n <= 10^9
Approaches
- Baseline: simulate and remember every row — time O(64 · 8), space O(64 · 8)
Follow-up
Detecting the cycle with a hash map works for any rule and any row length; the first use case changes the rule. The fixed period 14 is special to this rule on 8 cells, and the second use case shows how the period changes with the row length.
Related problems
Start free on Cariara · Coding problems · System design studio
