# Prison Cells After N Days

(Active and Inactive Cells After k Days)

`Array`

Medium

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.)

We describe the current state of the prison in the following way: `cells[i] == 1`if the`i`-th cell is occupied, else`cells[i] == 0`.

Given the initial state of the prison, return the state of the prison after`N`days (and`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]``````

Note:

1. `cells.length == 8`

2. `cells[i]`is in `{0, 1}`

3. `1 <= N <= 10^9`

## Analysis & Solution

### Brute-force Simulation

• Space: Extra Space: O(1) 不算返回答案所需的List

• Time: O(n * m), n - number of cells, m - days

！！注意：下面的代码在LeetCode会Time Limit Exceeded ！！

``````// IMPORT LIBRARY PACKAGES NEEDED BY YOUR PROGRAM
import java.util.List;
import java.util.LinkedList;
import java.util.Arrays;
// SOME CLASSES WITHIN A PACKAGE MAY BE RESTRICTED
// DEFINE ANY CLASS AND METHOD NEEDED
// CLASS BEGINS, THIS CLASS IS REQUIRED
public class Solution
{
// METHOD SIGNATURE BEGINS, THIS METHOD IS REQUIRED
public List<Integer> cellCompete(int[] states, int days)
{
// WRITE YOUR CODE HERE
if (states.length != 8 || days < 1) {
return convertToList(states);
}
int n = states.length;

int prevVal, nextVal;

while (days-- > 0) {

prevVal = 0;
nextVal = 0;

for (int i = 0; i < n; i++) {
if (i < n - 1) {
nextVal = states[i + 1];
} else if (i == n - 1) {
nextVal = 0;
}

if (nextVal == prevVal) {
prevVal = states[i];
states[i] = 0;
} else {
prevVal = states[i];
states[i] = 1;
}
}
}
return convertToList(states);
}
private List<Integer> convertToList(int[] arr) {
List<Integer> output = new LinkedList<Integer>();
for (int a: arr) {
output.add(a);
}
return output;
}
// METHOD SIGNATURE ENDS
}``````

``````class Solution {
public int[] prisonAfterNDays(int[] cells, int days) {
if (cells.length != 8 || days < 1) {
return cells;
}
int n = cells.length;

int prevVal, nextVal;

while (days-- > 0) {

prevVal = 0;
nextVal = 0;

for (int i = 0; i < n; i++) {
if (i == 0 || i == n - 1) {
prevVal = cells[i];
cells[i] = 0;
continue;
}
if (i < n - 1) {
nextVal = cells[i + 1];
} else if (i == n - 1) {
nextVal = 0;
}

if (nextVal == prevVal) {
prevVal = cells[i];
cells[i] = 1;
} else {
prevVal = cells[i];
cells[i] = 0;
}
}
}
return cells;
}
}``````

### 时间优化：找pattern

Time: O(n * m / k)

Space: O(n * k) - k 是循环周期，n是cells数，m是days

5069 ms, faster than 1.05%

``````class Solution {
public int[] prisonAfterNDays(int[] cells, int days) {
if (cells.length != 8 || days < 1) {
return cells;
}
int n = cells.length;

int prevVal, nextVal;
HashMap<String, Integer> map = new HashMap();
int period = -1;

while (days > 0) {

prevVal = 0;
nextVal = 0;

for (int i = 0; i < n; i++) {
if (i == 0 || i == n - 1) {
prevVal = cells[i];
cells[i] = 0;
continue;
}
if (i < n - 1) {
nextVal = cells[i + 1];
} else if (i == n - 1) {
nextVal = 0;
}

if (nextVal == prevVal) {
prevVal = cells[i];
cells[i] = 1;
} else {
prevVal = cells[i];
cells[i] = 0;
}
}
if (period < 0 ) {
String signature = Arrays.toString(cells);
if (map.containsKey(signature)) {
period = map.get(signature) - days;
while (period > 0 && days - period > 0) {
days -= period;
}
} else {
map.put(signature, days);
}
}
days--;
}
return cells;
}
}``````

### 时间优化才是重点，不做不必要的空间优化可以让代码更简洁：

13 ms, faster than 60.41%; 37.6 MB, less than 100.00%

``````class Solution {
public int[] prisonAfterNDays(int[] cells, int N) {
Map<String, Integer> 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 + 1;
}
}
return cells;
}
}``````

### 假设已经找到循环的Pattern周期为14之后，可以用如下方法：

``````public int[] prisonAfterNDays(int[] cells, int N) {
for (N = (N - 1) % 14 + 1; N > 0; --N) {
int[] cells2 = new int[8];
for (int i = 1; i < 7; ++i)
cells2[i] = cells[i - 1] == cells[i + 1] ? 1 : 0;
cells = cells2;
}
return cells;
}``````

## Reference

https://www.knowsh.com/Notes/250480/Active-And-Inactive-Cells-After-K-Days

https://www.geeksforgeeks.org/active-inactive-cells-k-days/

https://leetcode.com/problems/prison-cells-after-n-days/discuss/205684/JavaPython-Find-the-Loop-or-Mod-14

Last updated