Prison Cells After N Days
There are 8 prison cells in a row and each cell is either occupied or vacant.
Each day, whether each cell is occupied or vacant changes according to the following rules:
- If a cell has two adjacent neighbors that are both occupied or both vacant, then the cell becomes occupied.
- Otherwise, it becomes vacant.
Note that because the prison is a row, the first and the last cells in the row cannot have two adjacent neighbors.
You are given an integer array cells where cells[i] == 1 if the i^th cell is occupied and cells[i] == 0 if the i^th cell is vacant, and you are given an integer n.
Return the state of the prison after n days, after applying the changes described above once per day.
Example 1
Input
cells = [0,1,0,1,1,0,0,1], n = 7Output
[0,0,1,1,0,0,0,0]After applying the daily transition rules for 7 days, the prison state becomes [0, 0, 1, 1, 0, 0, 0, 0].
Example 2
Input
cells = [1,0,0,1,0,0,1,0], n = 1000000000Output
[0,0,1,1,1,1,1,0]After applying the daily transition rules for 1000000000 days, the prison state becomes [0, 0, 1, 1, 1, 1, 1, 0].
Constraints
- cells.length == 8
- cells[i] is either 0 or 1.
- 1 <= n <= 10^9