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 == 8cells[i]is either0or1.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;
}
}
Input
Output
#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
}
Input
Output
#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])]))
Input
Output
#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 < string, int>();
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;
}
}
}
Input
Output