# Prison Cells After N Days
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/prison-cells-after-n-days)
Canonical: https://scaleengineer.com/dsa/problems/prison-cells-after-n-days
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array, Hash Table
---
## Problem
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`

# Approaches
## Brute-force Simulation
This approach directly simulates the day-by-day changes of the prison cells for `n` days. It follows the rules given in the problem description in a straightforward manner without any optimizations.
**Time:** O(N * L), where N is the number of days and L is the number of cells. Since L is a constant (8), the time complexity is effectively O(N). Given that N can be as large as 10^9, this approach is too slow. · **Space:** O(L), where L is the number of cells. Since L is fixed at 8, the space complexity is O(1). This space is used for the temporary array to store the next state.
**Pros:** Simple to understand and implement.; Works correctly for small values of `n`.
**Cons:** Highly inefficient for large values of `n`.; Will result in a 'Time Limit Exceeded' (TLE) error on most platforms given the constraint `n <= 10^9`.
### Explanation
We iterate from day 1 to day `n`. In each iteration, we compute the state of the cells for the next day based on the current day's state. A temporary array, say `nextCells`, is used to store the new state to avoid modifying the current state while it's still being used for calculation. The rules are applied for each cell from index 1 to 6: `nextCells[i]` becomes 1 if `cells[i-1]` and `cells[i+1]` are the same, and 0 otherwise. The first and last cells (`cells[0]` and `cells[7]`) always become 0 as they don't have two neighbors. After calculating all the cells for the next day, the `cells` array is updated with the `nextCells` array. This process is repeated `n` times.

```java
class Solution {
    public int[] prisonAfterNDays(int[] cells, int n) {
        if (n == 0) {
            return cells;
        }

        int[] currentCells = cells;
        for (int i = 0; i < n; i++) {
            int[] nextCells = new int[8];
            // First and last cells become 0
            for (int j = 1; j < 7; j++) {
                if (currentCells[j - 1] == currentCells[j + 1]) {
                    nextCells[j] = 1;
                } else {
                    nextCells[j] = 0;
                }
            }
            currentCells = nextCells;
        }
        return currentCells;
    }
}
```
### Algorithm
*   Create a loop that iterates `n` times, representing `n` days.
*   Inside the loop, create a temporary array `nextCells` of size 8 to hold the state of the cells for the next day.
*   The first and last cells, `nextCells[0]` and `nextCells[7]`, are always set to 0 because they cannot have two adjacent neighbors.
*   Iterate through the inner cells from index 1 to 6.
*   For each cell `j`, calculate its next state based on its neighbors in the `currentCells` array: `nextCells[j] = (currentCells[j-1] == currentCells[j+1]) ? 1 : 0;`.
*   After computing all the states for the next day, update `currentCells` to be `nextCells`.
*   After the main loop of `n` iterations completes, `currentCells` will hold the final state of the prison.

## Simulation with Cycle Detection
The number of possible states for the prison cells is finite. Since the length of the array is fixed at 8, there are at most 2^8 = 256 possible states. This means the sequence of states must eventually repeat, forming a cycle. By detecting this cycle, we can mathematically determine the final state without simulating all `n` days, making the solution efficient for a large `n`.
**Time:** O(K * L), where K is the number of unique states and L is the number of cells. A cycle must be detected within K steps. Since K and L are constants, the time complexity is O(1). · **Space:** O(K * L), where K is the number of unique states and L is the number of cells. Since K is at most 2^8=256 and L=8, both are constants. Therefore, the space complexity is O(1).
**Pros:** Extremely efficient and handles very large `n`.; Correctly models the problem as a finite state machine with cycles.; Guaranteed to be fast because the number of states is constant and small.
**Cons:** Slightly more complex to implement due to the cycle detection logic and state management with a map.
### Explanation
The core idea is to simulate day by day while keeping track of the states we have already seen. A `HashMap` is perfect for this, mapping a state (represented as a string) to the day number on which it occurred.

We start the simulation. On each day `i`, we have the state `S_i`. We check if we have seen this state before. If we encounter a state `S_i` that's already in our map, say it first appeared on day `k` (i.e., `S_i == S_k`), we have found a cycle. The length of this cycle is `L = i - k`. We need to find the state after `n` days, `S_n`. We have already simulated `i` days. The number of remaining days is `n - i`. The final state will be the one that occurs after `(n - i) % L` steps into the cycle. We can then simulate these few remaining steps and return the result.

This approach avoids the TLE error because the number of unique states is small (at most 256), so a cycle is guaranteed to be found very quickly. The total number of simulations will be a small constant value, regardless of how large `n` is.

```java
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] prisonAfterNDays(int[] cells, int n) {
        Map<String, Integer> seen = new HashMap<>();

        for (int i = 0; i < n; i++) {
            String key = Arrays.toString(cells);
            if (seen.containsKey(key)) {
                int firstOccurrenceDay = seen.get(key);
                int cycleLength = i - firstOccurrenceDay;
                int remainingDays = n - i;
                int stepsToSimulate = remainingDays % cycleLength;

                for (int j = 0; j < stepsToSimulate; j++) {
                    cells = getNextState(cells);
                }
                return cells;
            }

            seen.put(key, i);
            cells = getNextState(cells);
        }

        return cells;
    }

    private int[] getNextState(int[] cells) {
        int[] nextCells = new int[8];
        for (int i = 1; i < 7; i++) {
            if (cells[i - 1] == cells[i + 1]) {
                nextCells[i] = 1;
            }
        }
        return nextCells;
    }
}
```
### Algorithm
*   Initialize a `HashMap<String, Integer>` to store a mapping from a cell state (as a String) to the day number it was first seen.
*   Start a loop to simulate day by day, from day `i = 0` up to `n-1`.
*   In each iteration, `cells` represents the state at day `i`. Convert the `cells` array to a string `key`.
*   Check if `key` already exists in the map. 
    *   If it does, a cycle is detected. Let the first time this state appeared be `firstOccurrenceDay`. The length of the cycle is `cycleLength = i - firstOccurrenceDay`.
    *   The number of remaining days to simulate is `remainingDays = n - i`.
    *   We only need to perform `remainingDays % cycleLength` more state transitions.
    *   Perform these remaining transitions and return the final state.
*   If `key` is not in the map, store the current state and day: `map.put(key, i)`.
*   Calculate the next state of `cells` for day `i+1`.
*   If the loop finishes without finding a cycle (because `n` was small), the final `cells` array is the answer.

# Solutions
### Java

```java
class Solution {
public
  int[] prisonAfterNDays(int[] cells, int N) {
    Map<String, Integer> stateDayMap = new HashMap<String, Integer>();
    Map<Integer, int[]> dayStateMap = new HashMap<Integer, int[]>();
    int[] prevCells = new int[8];
    System.arraycopy(cells, 0, prevCells, 0, 8);
    int days = 0;
    int cycle = 0;
    while (days < N) {
      days++;
      int[] change = new int[8];
      change[0] = 0;
      change[7] = 0;
      for (int i = 1; i < 7; i++) {
        if (prevCells[i - 1] == prevCells[i + 1])
          change[i] = 1;
      }
      for (int i = 0; i < 8; i++)
        prevCells[i] = change[i];
      String arrayStr = Arrays.toString(change);
      if (stateDayMap.containsKey(arrayStr)) {
        int prevDay = stateDayMap.get(arrayStr);
        cycle = days - prevDay;
        break;
      } else {
        stateDayMap.put(arrayStr, days);
        dayStateMap.put(days, change);
      }
    }
    if (days == N)
      return prevCells;
    int remainder = N % cycle;
    if (remainder == 0)
      remainder = cycle;
    return dayStateMap.get(remainder);
  }
}

```

### Python

```python
class Solution (object):
    def prisonAfterNDays(self, oldcells, N): """ :type cells: List[int] :type N: int :rtype: List[int] """ cells = copy . deepcopy(oldcells) count = 0 N %= 14 if N == 0: N = 14 while count < N: newCell = [0] * 8 for i in range(1, 7): if cells[i - 1] == cells[i + 1]: newCell[i] = 1 else: newCell[i] = 0 cells = newCell count += 1 return cells

```

### CPP

```cpp
// OJ: https://leetcode.com/problems/prison-cells-after-n-days/ // Time: O(1) // Space: O(1) class Solution { char next ( char c ) { char ans = 0 ; for ( int i = 1 ; i < 7 ; ++ i ) ans |= (( c >> ( i - 1 ) & 1 ) == ( c >> ( i + 1 ) & 1 )) << i ; return ans ; } public: vector < int > prisonAfterNDays ( vector < int >& A , int N ) { char c = 0 ; for ( int i = 0 ; i < 8 ; ++ i ) c |= A [ i ] << i ; vector < char > v { c }; unordered_map < char , int > m { { c , 0 } }; for ( int i = 1 ; i <= N ; ++ i ) { c = next ( c ); if ( m . count ( c )) { int d = i - m [ c ]; c = v [( N - i ) % d + m [ c ]]; break ; } v . push_back ( c ); m [ c ] = i ; } vector < int > ans ( 8 ); for ( int i = 0 ; i < 8 ; ++ i ) ans [ i ] = ( c >> i ) & 1 ; return ans ; } };
```