# 957.Prison-Cells-After-N-Days

## ้ข็ฎๅฐๅ

https://leetcode.com/problems/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.)

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]

## ไปฃ็ 

### Approach #2 find the loop

Note that cells.length = 8, and cells[0] and cells[7] will become 0. In fact, cells have only 2 ^ 6 = 64 different states. And there will be a loop.

Well, the length of loop can be 1, 7, or 14.

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

return cells;
}
}

### Approach #2 Simulation

class Solution {
public int[] prisonAfterNDays(int[] cells, int N) {
Map<Integer,int[]> map = new HashMap<Integer,int[]>();
int days = N;
int cycle = 0;
while(days-- > 0){
int[] nextDay = new int[8];
for(int i = 1; i < 7; i++){
nextDay[i] = cells[i - 1] == cells[i + 1] ? 1 : 0;
}
int[] first = map.getOrDefault(1, null);
if(first != null){
if(Arrays.equals(nextDay, first)){
if(N % (N - days - 1) == 0)
return cells;
break;
}
}
map.put(N - days, nextDay);
cells = nextDay;
}
return days == -1 ? cells : map.get(N % (N - days - 1));
}
}

Approach 3: Time Limit Exceeded

class Solution {
public int[] prisonAfterNDays(int[] cells, int N) {
int n = cells.length;
int temp[] = new int[n];

while (N > 0) {
for (int i = 0; i < n; i++) {
temp[i] = cells[i];
}

temp[0] = 0;
temp[n - 1] = 0;

for (int i = 1; i <= n - 2; i++) {
if (cells[i - 1] == cells[i + 1]) {
temp[i] = 1;
} else {
temp[i] = 0;
}
}

for (int i = 0; i < n; i++) {
cells[i] = temp[i];
}

N--;
}

return cells;
}
}

Last updated