1. Problem Description

You are given an array cells of length 8, where each cell can be either occupied (1) or vacant (0).
Each day, every cell changes state based on the following rule:

• A cell becomes occupied (1) if its two adjacent cells were both occupied or both vacant on the previous day.
• Otherwise, it becomes vacant (0).
• The first and last cells (index 0 and 7) will always become 0 because they have only one neighbor.

Given an integer N, you need to return the state of the prison after N days.

---

2. Example

Input:
cells = [0,1,0,1,1,0,0,1], N = 7

Output:
[0,0,1,1,0,0,0,0]

---

3. Intuition

The problem appears simple, but N can be very large (up to 10^9), so simulating day by day is inefficient.
However, because there are only 8 cells, there are only 2⁶ = 64 possible internal states (since first and last are always 0).
Thus, the pattern will repeat in a cycle.

We can exploit this periodicity:

1. Detect the cycle.
2. Reduce N modulo the cycle length.
3. Compute only the remaining steps.

---

4. Algorithm

1. Initialize a HashMap to store previously seen cell states and the day count.
2. For each day:
   • Compute the next day’s state using the transformation rule.
   • If this state has been seen before, calculate the cycle length.
   • Reduce N modulo the cycle length.
   • Simulate only the remaining N days.
3. Return the final cell state.

---

5. Code Implementation (Java)

import java.util.*;

public class PrisonCellsAfterNDays {
    public int[] prisonAfterNDays(int[] cells, int N) {
        Map<String, Integer> seen = new HashMap<>();
        boolean cycleFound = false;
        int cycleLength = 0;

        while (N > 0) {
            String state = Arrays.toString(cells);
            if (seen.containsKey(state)) {
                cycleFound = true;
                cycleLength = seen.get(state) - N;
                N %= cycleLength;
            } else {
                seen.put(state, N);
            }

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

    private int[] nextDay(int[] cells) {
        int[] newCells = new int[8];
        for (int i = 1; i < 7; i++) {
            newCells[i] = cells[i - 1] == cells[i + 1] ? 1 : 0;
        }
        return newCells;
    }

    public static void main(String[] args) {
        PrisonCellsAfterNDays obj = new PrisonCellsAfterNDays();
        int[] cells = {0,1,0,1,1,0,0,1};
        int N = 7;
        System.out.println(Arrays.toString(obj.prisonAfterNDays(cells, N)));
    }
}

---

6. Dry Run

Let’s dry-run the example:

Input:
cells = [0,1,0,1,1,0,0,1], N = 7

Day	Previous State	Computation (compare i-1 and i+1)	New State
0	[0,1,0,1,1,0,0,1]	–	[0,1,0,1,1,0,0,1]
1		1: 0≠0 →0, 2:1≠1→0, 3:0=0→1, 4:1≠0→0, 5:1=0→0, 6:0≠1→0	[0,0,1,0,0,0,0,0]
2	[0,0,1,0,0,0,0,0]	1:0=1→1, 2:0≠0→0, 3:1≠0→0, 4:0=0→1, 5:0=0→1, 6:0=0→1	[0,1,0,0,1,1,1,0]
3	[0,1,0,0,1,1,1,0]	Compute similarly → [0,0,0,0,0,1,1,0]
4	[0,0,0,0,0,1,1,0]	→ [0,0,0,1,1,0,0,0]
5	[0,0,0,1,1,0,0,0]	→ [0,0,1,0,0,0,0,0]
6	[0,0,1,0,0,0,0,0]	→ [0,1,0,0,1,1,1,0]
7	[0,1,0,0,1,1,1,0]	→ [0,0,1,1,0,0,0,0]

Final Output: [0,0,1,1,0,0,0,0]

---

7. Time and Space Complexity

• Time Complexity: O(1) after detecting the cycle (at most 64 unique states).
• Space Complexity: O(1) or O(64) for the map of seen states.

---

8. Key Insights

• Even with huge N, you only need to simulate up to 64 states due to repetition.
• Bitmasking can further optimize this, but the array-based approach is clear and fast enough.