## Algorithm

Problem Name: 957. Prison Cells After N Days

There are `8` prison cells in a row and each cell is either occupied or vacant.

Each day, whether the 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 can't have two adjacent neighbors.

You are given an integer array `cells` where `cells[i] == 1` if the `ith` cell is occupied and `cells[i] == 0` if the `ith` cell is vacant, and you are given an integer `n`.

Return the state of the prison after `n` days (i.e., `n` such changes described above).

Example 1:

```Input: cells = [0,1,0,1,1,0,0,1], n = 7
Output: [0,0,1,1,0,0,0,0]
Explanation: The following table summarizes the state of the prison on each day:
Day 0: [0, 1, 0, 1, 1, 0, 0, 1]
Day 1: [0, 1, 1, 0, 0, 0, 0, 0]
Day 2: [0, 0, 0, 0, 1, 1, 1, 0]
Day 3: [0, 1, 1, 0, 0, 1, 0, 0]
Day 4: [0, 0, 0, 0, 0, 1, 0, 0]
Day 5: [0, 1, 1, 1, 0, 1, 0, 0]
Day 6: [0, 0, 1, 0, 1, 1, 0, 0]
Day 7: [0, 0, 1, 1, 0, 0, 0, 0]
```

Example 2:

```Input: cells = [1,0,0,1,0,0,1,0], n = 1000000000
Output: [0,0,1,1,1,1,1,0]
```

Constraints:

• `cells.length == 8`
• `cells[i]` is either `0` or `1`.
• `1 <= n <= 109`

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int[] prisonAfterNDays(int[] cells, int N) {
Map seen = new HashMap<>();
while (N > 0) {
int[] cells2 = new int[8];
seen.put(Arrays.toString(cells), N--);
for (int i = 1; i < 7; ++i) {
cells2[i] = cells[i - 1] == cells[i + 1] ? 1 : 0;
}
cells = cells2;
if (seen.containsKey(Arrays.toString(cells))) {
N %= seen.get(Arrays.toString(cells)) - N;
}
}
return cells;
}
}
``````
Copy The Code &

Input

cmd
cells = [0,1,0,1,1,0,0,1], n = 7

Output

cmd
[0,0,1,1,0,0,0,0]

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const prisonAfterNDays = function (cells, N) {
const temp = [...cells]
const maxIter = 2 * cells.length - 2
N = N % maxIter === 0 ? maxIter : N % maxIter
while (N > 0) {
for (let i = 0; i < cells.length; i++) {
temp[i] = cells[i - 1] === cells[i + 1] ? 1 : 0
}
cells = [...temp]
N--
}
return cells
}
``````
Copy The Code &

Input

cmd
cells = [0,1,0,1,1,0,0,1], n = 7

Output

cmd
[0,0,1,1,0,0,0,0]

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def prisonAfterNDays(self, cells, N):
day, state, cur = 0, {}, "".join(map(str, cells))
while cur not in state:
state[cur] = day
state[day] = cur
if day == N:
return list(map(int, cur))
day += 1
cur = "0" + "".join(cur[i - 1] == cur[i + 1] and "1" or "0" for i in range(1, len(cur) - 1)) + "0"
return list(map(int, state[state[cur] + (N - state[cur]) % (day - state[cur])]))
``````
Copy The Code &

Input

cmd
cells = [1,0,0,1,0,0,1,0], n = 1000000000

Output

cmd
[0,0,1,1,1,1,1,0]

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;

namespace LeetCode
{
public class _0957_PrisonCellsAfterNDays
{
public int[] PrisonAfterNDays(int[] cells, int N)
{
var cache = new Dictionary();
var fastForward = false;

while (N > 0)
{
if (!fastForward)
{
var key = string.Join(",", cells);
if (cache.ContainsKey(key))
{
var length = cache[key] - N;
N %= length;
fastForward = true;
}
else
cache.Add(key, N);
}

if (N > 0)
{
cells = NextDay(cells);
N--;
}
}

return cells;
}

private int[] NextDay(int[] cells)
{
int[] newCells = new int[cells.Length];
newCells[0] = 0;
for (int i = 1; i < cells.Length - 1; i++)
newCells[i] = (cells[i - 1] == cells[i + 1]) ? 1 : 0;
newCells[cells.Length - 1] = 0;
return newCells;
}
}
}
``````
Copy The Code &

Input

cmd
cells = [1,0,0,1,0,0,1,0], n = 1000000000

Output

cmd
[0,0,1,1,1,1,1,0]