Prison Cells After N Days

MediumProblemExternal linkUpdated Sep 25, 2026

Description

There are 8 prison cells in a row, numbered 0 to 7. Each cell is either occupied (1) or vacant (0). Every day, all the cells change at the same moment, following one rule:

A cell becomes occupied if its two neighbours were both occupied or both vacant the day before.
Otherwise, it becomes vacant.

Cells 0 and 7 have only one neighbour each, so they can never have two neighbours that match: from the first day on, they are vacant.

You are given the starting row cells, where cells[i] is 1 if cell i is occupied and 0 if it is vacant, and a number n. Return the row after n days.

Examples

Example 1

Input: cells = [1, 1, 0, 0, 1, 0, 1, 0], n = 3

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

Explanation:

day 0:  1 1 0 0 1 0 1 0
day 1:  0 0 0 0 1 1 1 0
day 2:  0 1 1 0 0 1 0 0
day 3:  0 0 0 0 0 1 0 0

For example, cell 4 is occupied on day 1 because its neighbours on day 0, cells 3 and 5, are both vacant. Cell 3 is vacant on day 1 because its neighbours, cells 2 and 4, differ.

Example 2

Input: cells = [1, 1, 0, 0, 1, 0, 1, 0], n = 1000000000

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

Explanation: The same starting row as Example 1, but a billion days. From day 1 on the rows repeat every 14 days, so day 1,000,000,000 has the same row as day (1,000,000,000 − 1) % 14 + 1 = day 6, which is 0 0 1 1 0 0 0 0.

Example 3

Input: cells = [1, 0, 0, 0, 0, 0, 0, 1], n = 14

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

Explanation: Day 1 is 0 0 1 1 1 1 0 0, and day 14 is 0 1 1 1 1 1 1 0. Day 14 is not the starting row: the start has both end cells occupied, and no row after day 0 can.

Constraints

cells.length == 8
cells[i] is either 0 or 1.
1 ≤ n ≤ 10^9

Editorial

Brute Force

Intuition

Do what the question describes: build each day's row from the day before, n times.

One day. For each inner cell i, from 1 to 6, look at cells i − 1 and i + 1 of today's row. If they are equal, cell i is 1 tomorrow; if they differ, it is 0. The cell's own value today plays no part. Cells 0 and 7 are 0 tomorrow, always.

Four cases of the rule: neighbours 0 and 0 or 1 and 1 make the cell occupied tomorrow, neighbours 0 and 1 or 1 and 0 make it vacant, whatever the cell itself holds. Below, Example 1 goes from day 0, 1 1 0 0 1 0 1 0, to day 1, 0 0 0 0 1 1 1 0, with both end cells vacant because each has only one neighbour.

Build tomorrow in a new row. Every cell changes at the same moment, so every cell must be worked out from today's row. If you write tomorrow's values into the same list as you go, cell i + 1 reads the new value of cell i instead of today's. On Example 1, updating in place turns day 0 into 0 0 1 1 0 0 1 0 instead of the correct 0 0 0 0 1 1 1 0.

Step-by-Step Explanation

We trace Example 1, cells = [1, 1, 0, 0, 1, 0, 1, 0] and n = 3. The top row is today; the row underneath is tomorrow, filled in cell by cell on day 1. The two neighbours being compared turn green when they match and orange when they differ. Days 2 and 3 are shown whole.

Step 1: Day 0 is 1 1 0 0 1 0 1 0. Tomorrow is built in a separate row.

Step 2: Cells 0 and 7 have one neighbour each, so both are 0 tomorrow.

Step 3: Cell 1: neighbours 1 and 0 differ, so it becomes 0.

Step 4: Cell 2: neighbours 1 and 0 differ, so it becomes 0.

Step 5: Cell 3: neighbours 0 and 1 differ, so it becomes 0.

Step 6: Cell 4: neighbours 0 and 0 match, so it becomes 1.

Step 7: Cell 5: neighbours 1 and 1 match, so it becomes 1.

Step 8: Cell 6: neighbours 0 and 0 match, so it becomes 1.

Step 9: Day 1 0 0 0 0 1 1 1 0 becomes day 2 0 1 1 0 0 1 0 0.

Step 10: Day 2 0 1 1 0 0 1 0 0 becomes day 3 0 0 0 0 0 1 0 0.

Step 11: After 3 days the row is 0 0 0 0 0 1 0 0. Return it.

Brute Force — Building Each Day From the One Before — Example 1: today's row on top, tomorrow's row underneath. Day 1 is built cell by cell from each cell's two neighbours; days 2 and 3 are shown whole.

Algorithm

Repeat n times:
- Make a new row next of eight 0s.
- For i from 1 to 6: next[i] = 1 if cells[i − 1] == cells[i + 1], otherwise 0.
- Set cells = next.
Return cells.

Code

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> prisonAfterNDays(vector<int>& cells, int n) {
        for (int day = 0; day < n; day++) {
            vector<int> next(8, 0);  // an end cell has only one neighbour, so it is always vacant
            for (int i = 1; i < 7; i++) next[i] = cells[i - 1] == cells[i + 1];
            cells = next;  // a new row: updating in place would read neighbours already changed today
        }
        return cells;
    }
};

class Solution:
    def prisonAfterNDays(self, cells: list[int], n: int) -> list[int]:
        for _ in range(n):
            nxt = [0] * 8  # an end cell has only one neighbour, so it is always vacant
            for i in range(1, 7):
                nxt[i] = 1 if cells[i - 1] == cells[i + 1] else 0
            cells = nxt  # a new row: updating in place would read neighbours already changed today
        return cells

class Solution {
    public int[] prisonAfterNDays(int[] cells, int n) {
        for (int day = 0; day < n; day++) {
            int[] next = new int[8];  // an end cell has only one neighbour, so it is always vacant
            for (int i = 1; i < 7; i++) next[i] = cells[i - 1] == cells[i + 1] ? 1 : 0;
            cells = next;  // a new row: updating in place would read neighbours already changed today
        }
        return cells;
    }
}

Complexity Analysis

Time Complexity: O(n). Each day costs 6 comparisons and a new row of 8 cells, a fixed amount of work, and there are n days.

Space Complexity: O(1). Two rows of 8 cells.

Why This Approach Is Not Efficient

n can be as large as 10^9. Measured, running all 10^9 days of Example 2 takes about 184 seconds in Python and 17 seconds in C++. The work grows with n, even though the row only ever has 8 cells.

That mismatch is the clue. A row of 8 cells, each 0 or 1, can only be one of 2^8 = 256 patterns. From day 1 on, the two end cells are always 0, so only the 6 inner cells vary: at most 2^6 = 64 different rows. Over a billion days, the same few rows must come back again and again. And because each day's row depends only on the day before, once a row comes back, everything after it repeats exactly as it did the first time.

Better Approach - Remember Every Row and Jump Over the Loop

Intuition

Rows must repeat. After day 1 there are at most 64 possible rows, so among days 1 to 65 some row must appear twice: 65 days, but only 64 rows to fill them. (This is the pigeonhole idea: put 65 letters into 64 boxes and some box gets two.)

A repeat means a loop. Tomorrow's row depends only on today's. So if the row from day a comes back on day b, then day b + 1 equals day a + 1, day b + 2 equals day a + 2, and so on forever. From day a on, the rows run round a loop of b − a days. For Example 1's starting row, day 15 is day 1 again:

The rows of Example 1 drawn as a loop: day 0, 1 1 0 0 1 0 1 0, leads in and never returns because its first cell is occupied; days 1 to 7 run down the left and days 8 to 14 up the right, and day 15 is day 1 again. The row on day n is the row on day (n − 1) % 14 + 1.

Jump over the loop. Keep a hash map from each row to the day it first appeared. When today's row is already in the map, the loop is today − first day. Going once round the loop brings you back to today's row, so whole laps change nothing and only the remainder matters: (n − today) % loop more days. Simulate just those.

A list cannot be a dictionary key in Python, so the Python code stores the row as a tuple. C++ can use the vector itself as a map key, and the Java code uses the row written out as text by Arrays.toString.

Step-by-Step Explanation

We trace Example 2: the same starting row, with n = 1,000,000,000. Today's row is on top. The table is the map from each row seen so far, written as a string, to the day it first appeared, and the line underneath is the lookup of today's row.

Step 1: Day 0: 11001010 is new. Store it with day 0.

Step 2: Day 1: 00001110 is new. Store it with day 1.

Step 3: Day 2: 01100100 is new. Store it with day 2.

Step 4: Day 3: 00000100 is new. Store it with day 3.

Step 5: Day 4: 01110100 is new. Store it with day 4.

Step 6: Day 5: 00101100 is new. Store it with day 5.

Step 7: Day 6: 00110000 is new. Store it with day 6.

Step 8: Day 7: 00000110 is new. Store it with day 7.

Step 9: Day 8: 01110000 is new. Store it with day 8.

Step 10: Day 9: 00100110 is new. Store it with day 9.

Step 11: Day 10: 00100000 is new. Store it with day 10.

Step 12: Day 11: 00101110 is new. Store it with day 11.

Step 13: Day 12: 00110100 is new. Store it with day 12.

Step 14: Day 13: 00001100 is new. Store it with day 13.

Step 15: Day 14: 01100000 is new. Store it with day 14.

Step 16: Day 15: 00001110 is already stored, from day 1. The loop is 15 − 1 = 14 days, and (1,000,000,000 − 15) % 14 = 5 days remain.

Step 17: Run 5 more days, reaching day 20: 0 0 1 1 0 0 0 0. Return it, after 20 simulated days out of a billion.

Remember Rows Until One Repeats, Then Jump — Example 2: today's row on top and the map from each row seen so far to the day it first appeared; the line underneath is the lookup of today's row.

Algorithm

Let seen be an empty map from row to day, and day = 0.
While day < n:
- If cells is already in seen: set loop = day − seen[cells], move cells forward (n − day) % loop more days, and return it.
- Otherwise store seen[cells] = day, move cells to the next day, and add 1 to day.
Return cells. This is reached only when n comes before the first repeat.

Code

#include <map>
#include <vector>
using namespace std;

class Solution {
    vector<int> nextDay(const vector<int>& cells) {
        vector<int> next(8, 0);
        for (int i = 1; i < 7; i++) next[i] = cells[i - 1] == cells[i + 1];
        return next;
    }

public:
    vector<int> prisonAfterNDays(vector<int>& cells, int n) {
        map<vector<int>, int> seen;  // row -> the first day it appeared
        for (int day = 0; day < n; day++) {
            auto it = seen.find(cells);
            if (it != seen.end()) {
                int loop = day - it->second;
                for (int k = (n - day) % loop; k > 0; k--) cells = nextDay(cells);
                return cells;
            }
            seen[cells] = day;
            cells = nextDay(cells);
        }
        return cells;
    }
};

class Solution:
    def prisonAfterNDays(self, cells: list[int], n: int) -> list[int]:
        seen = {}  # row -> the first day it appeared
        day = 0
        while day < n:
            row = tuple(cells)
            if row in seen:
                loop = day - seen[row]
                for _ in range((n - day) % loop):
                    cells = self.next_day(cells)
                return cells
            seen[row] = day
            cells = self.next_day(cells)
            day += 1
        return cells

    def next_day(self, cells: list[int]) -> list[int]:
        return [0] + [1 if cells[i - 1] == cells[i + 1] else 0 for i in range(1, 7)] + [0]

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<>();  // row -> the first day it appeared
        for (int day = 0; day < n; day++) {
            String row = Arrays.toString(cells);
            Integer first = seen.get(row);
            if (first != null) {
                int loop = day - first;
                for (int k = (n - day) % loop; k > 0; k--) cells = nextDay(cells);
                return cells;
            }
            seen.put(row, day);
            cells = nextDay(cells);
        }
        return cells;
    }

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

Complexity Analysis

Time Complexity: O(1), whatever the size of n. The counting above guarantees a repeat by day 65, and checking all 256 possible starting rows shows it always comes by day 15. After that, fewer than one loop's worth of days are simulated. So n = 10^9 costs the same as n = 20.

Space Complexity: O(1). At most 65 rows could be stored; in practice never more than 15.

Why This Approach Is Not Efficient

This is already fast: measured in Python, n = 10^9 takes about 5.5 microseconds. What it still spends:

A map of up to 15 rows, with every row turned into a key and hashed, only to discover the length of the loop.
Two phases of simulation and a remainder worked out while running.

And the loop it discovers is always one of the same few lengths. Checking all 256 starting rows shows the loop is 14 days for 224 of them, 7 days for 28 and 1 day for the last 4, and both 7 and 1 divide 14. So from day 1 on, every row repeats every 14 days, whatever the start. Knowing that in advance makes the map unnecessary.

(A loop can also be found without storing rows, by running two copies of the days, one a day at a time and one two days at a time, until they meet. This is known as the tortoise and the hare. Here there is nothing left to find: the loop length is already known.)

Optimal Approach - Every Row Repeats Every 14 Days

Intuition

Idea 1: the loop always fits in 14 days. From day 1 on, every row comes back after 14 days: after exactly 14, or after 7 or 1, which also divide 14. This is not a guess from a few examples. There are only 256 possible starting rows, and checking every one of them confirms it. So

row on day n = row on day (n − 1) % 14 + 1

Why (n − 1) % 14 + 1 and not n % 14? Day 0 is not on the loop: its end cells may be occupied, and no later day allows that. The loop is days 1 to 14, so n must be turned into a day from 1 to 14, never 0. Example 3 is the trap: with n = 14, n % 14 runs 0 days and returns the starting row 1 0 0 0 0 0 0 1, but day 14 is 0 1 1 1 1 1 1 0.

So run at most 14 days, whatever n is, with no map and no search for the loop.

Where 14 comes from (optional). The check over all 256 rows settles the question, but there is also a reason behind it.

The row 0 0 1 0 0 1 0 0 never changes: each of its inner cells is 1 exactly when its two neighbours match. Call it F.
Mark the cells where a row differs from F. Because the row and F follow the same rule, the marks follow a simpler rule of their own: tomorrow, a cell is marked exactly when one of its two neighbours is marked today, but not both. The "neighbours match" part of the original rule cancels out.
The six inner cells behave like half of a ring of 14 cells: the two always-empty end cells and a mirror copy of the six, going round. On that ring, the marks follow the same simple rule.
That rule doubles neatly. Two days of it mark a cell when exactly one of the cells two places away is marked, four days four places away, eight days eight places away, sixteen days sixteen places away. The ways of reaching a cell twice cancel in pairs.
On a ring of 14, sixteen places round is the same as two places. So 16 days of marks equal 2 days.
Among rows with empty end cells, each has exactly one row before it, so days can be undone. Undo 2 days on both sides of "16 days = 2 days", and 14 days = no change at all.

Idea 2: a whole day in one line. Put the 8 cells into the bits of one number x, with cell 0 as the highest bit. x << 1 moves every bit one place towards cell 0, so each cell now holds the value of its right neighbour. x >> 1 moves them the other way, so each cell holds its left neighbour. XOR of the two is 1 exactly where the two neighbours differ; NOT turns that into 1 exactly where they match, which is the rule. Finally, & 0b01111110 empties the two end cells.

Day 1 of Example 1, 0 0 0 0 1 1 1 0, becomes day 2 in bit operations: shifted left it gives each cell its right neighbour, 0 0 0 1 1 1 0 0; shifted right its left neighbour, 0 0 0 0 0 1 1 1; XOR gives 1 where they differ, 0 0 0 1 1 0 1 1; NOT gives 1 where they match, 1 1 1 0 0 1 0 0; and the mask 01111110 empties the end cells, giving day 2, 0 1 1 0 0 1 0 0.

Step-by-Step Explanation

We trace Example 2, n = 1,000,000,000, with the row held as 8 bits. First the number of days to run is worked out. Day 2 is then shown in slow motion, one bit operation at a time, with the operation's inputs in the rows underneath; every other day is a single line.

Step 1: (1,000,000,000 − 1) % 14 + 1 = 6, so only 6 days run. Pack the row into x = 11001010 = 202.

Step 2: Day 1: one line turns 11001010 into 00001110.

Step 3: Shift both ways: x << 1 = 00011100 holds each right neighbour, x >> 1 = 00000111 each left neighbour.

Step 4: XOR them: 00011011, a 1 wherever the two neighbours differ.

Step 5: Flip with NOT: 11100100, a 1 wherever the neighbours match. Cell 0 is wrongly 1.

Step 6: AND with 01111110 empties both ends: day 2 is 01100100.

Step 7: Day 3: 00000100.

Step 8: Day 4: 01110100.

Step 9: Day 5: 00101100.

Step 10: Day 6: 00110000.

Step 11: Unpack and return 0 0 1 1 0 0 0 0.

Six Days Instead of a Billion, One Bit Line per Day — Example 2 with the row held as 8 bits. Day 2 is broken into its shift, XOR, NOT and mask; every other day is one line.

Algorithm

Pack the row into a number: start with x = 0, and for each cell c in order, x = (x << 1) | c. Cell 0 ends up as the highest of the 8 bits.
Let days = (n − 1) % 14 + 1, a number from 1 to 14.
Repeat days times: x = ~((x << 1) ^ (x >> 1)) & 0b01111110.
Unpack: cell i is (x >> (7 − i)) & 1.

Why the mask is needed. ~ flips every bit of the number, including the ones above the 8 cells, so the result is no longer an 8-bit value; in all three languages it becomes negative. The mask keeps bits 1 to 6 and clears everything else, including the two end cells, which the rule says must be 0. On day 2 of Example 2 above, NOT alone would leave cell 0 occupied.

Why (n − 1) % 14 + 1. n % 14 gives 0 whenever n is a multiple of 14, which runs no days at all and returns the starting row, as Example 3 shows.

Code

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> prisonAfterNDays(vector<int>& cells, int n) {
        int x = 0;
        for (int c : cells) x = (x << 1) | c;  // cells[0] ends up as the highest of the 8 bits
        for (int day = (n - 1) % 14 + 1; day > 0; day--)  // from day 1 on, every row repeats every 14 days
            x = ~((x << 1) ^ (x >> 1)) & 0b01111110;  // 1 where the two neighbours match; the mask empties both ends
        vector<int> out(8);
        for (int i = 0; i < 8; i++) out[i] = (x >> (7 - i)) & 1;
        return out;
    }
};

class Solution:
    def prisonAfterNDays(self, cells: list[int], n: int) -> list[int]:
        x = 0
        for c in cells:  # cells[0] ends up as the highest of the 8 bits
            x = (x << 1) | c
        for _ in range((n - 1) % 14 + 1):  # from day 1 on, every row repeats every 14 days
            x = ~((x << 1) ^ (x >> 1)) & 0b01111110  # 1 where the two neighbours match; the mask empties both ends
        return [(x >> (7 - i)) & 1 for i in range(8)]

class Solution {
    public int[] prisonAfterNDays(int[] cells, int n) {
        int x = 0;
        for (int c : cells) x = (x << 1) | c;  // cells[0] ends up as the highest of the 8 bits
        for (int day = (n - 1) % 14 + 1; day > 0; day--)  // from day 1 on, every row repeats every 14 days
            x = ~((x << 1) ^ (x >> 1)) & 0b01111110;  // 1 where the two neighbours match; the mask empties both ends
        int[] out = new int[8];
        for (int i = 0; i < 8; i++) out[i] = (x >> (7 - i)) & 1;
        return out;
    }
}

Complexity Analysis

Time Complexity: O(1). At most 14 days, each a handful of bit operations, plus packing and unpacking 8 cells. Measured in Python, n = 10^9 takes about 0.6 microseconds.

Space Complexity: O(1). One integer.