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).

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

1
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 <= 10^9

Solution

Method 1 – Cycle Detection and Simulation

Intuition

Since there are only 8 cells, there are at most 2^6 = 64 possible states (since the first and last are always 0 after the first day). We can use a hash map to detect cycles and fast-forward the simulation.

Approach

  1. Simulate each day, storing the state in a map from tuple to day.
  2. If a cycle is detected, fast-forward n by the cycle length.
  3. Continue simulation for the remaining days.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    vector<int> prisonAfterNDays(vector<int>& cells, int n) {
        unordered_map<string, int> seen;
        vector<int> curr = cells;
        while (n > 0) {
            string key(curr.begin(), curr.end());
            if (seen.count(key)) {
                n %= seen[key] - n;
            }
            seen[key] = n;
            if (n > 0) {
                vector<int> next(8);
                for (int i = 1; i < 7; ++i)
                    next[i] = curr[i-1] == curr[i+1];
                curr = next;
                --n;
            }
        }
        return curr;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func prisonAfterNDays(cells []int, n int) []int {
    seen := map[string]int{}
    curr := append([]int{}, cells...)
    for n > 0 {
        key := fmt.Sprint(curr)
        if v, ok := seen[key]; ok {
            n %= v - n
        }
        seen[key] = n
        if n > 0 {
            next := make([]int, 8)
            for i := 1; i < 7; i++ {
                if curr[i-1] == curr[i+1] { next[i] = 1 }
            }
            curr = next
            n--
        }
    }
    return curr
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

import java.util.*;
class Solution {
    public int[] prisonAfterNDays(int[] cells, int n) {
        Map<String, Integer> seen = new HashMap<>();
        int[] curr = Arrays.copyOf(cells, 8);
        while (n > 0) {
            String key = Arrays.toString(curr);
            if (seen.containsKey(key)) {
                n %= seen.get(key) - n;
            }
            seen.put(key, n);
            if (n > 0) {
                int[] next = new int[8];
                for (int i = 1; i < 7; ++i)
                    next[i] = curr[i-1] == curr[i+1] ? 1 : 0;
                curr = next;
                --n;
            }
        }
        return curr;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    fun prisonAfterNDays(cells: IntArray, n: Int): IntArray {
        val seen = mutableMapOf<String, Int>()
        var curr = cells.copyOf()
        var days = n
        while (days > 0) {
            val key = curr.joinToString(",")
            if (seen.containsKey(key)) {
                days %= seen[key]!! - days
            }
            seen[key] = days
            if (days > 0) {
                val next = IntArray(8)
                for (i in 1..6) next[i] = if (curr[i-1] == curr[i+1]) 1 else 0
                curr = next
                days--
            }
        }
        return curr
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

from typing import List
class Solution:
    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:
        seen = dict()
        curr = tuple(cells)
        while n > 0:
            if curr in seen:
                n %= seen[curr] - n
            seen[curr] = n
            if n > 0:
                nextc = [0]*8
                for i in range(1,7):
                    nextc[i] = int(curr[i-1] == curr[i+1])
                curr = tuple(nextc)
                n -= 1
        return list(curr)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

use std::collections::HashMap;
impl Solution {
    pub fn prison_after_n_days(mut cells: Vec<i32>, mut n: i32) -> Vec<i32> {
        let mut seen = HashMap::new();
        while n > 0 {
            let key = cells.clone();
            if let Some(&v) = seen.get(&key) {
                n %= v - n;
            }
            seen.insert(key.clone(), n);
            if n > 0 {
                let mut next = vec![0; 8];
                for i in 1..7 {
                    if cells[i-1] == cells[i+1] { next[i] = 1; }
                }
                cells = next;
                n -= 1;
            }
        }
        cells
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    prisonAfterNDays(cells: number[], n: number): number[] {
        const seen = new Map<string, number>();
        let curr = cells.slice();
        while (n > 0) {
            const key = curr.join(',');
            if (seen.has(key)) {
                n %= seen.get(key)! - n;
            }
            seen.set(key, n);
            if (n > 0) {
                const next = Array(8).fill(0);
                for (let i = 1; i < 7; ++i)
                    next[i] = curr[i-1] === curr[i+1] ? 1 : 0;
                curr = next;
                --n;
            }
        }
        return curr;
    }
}

Complexity

  • ⏰ Time complexity: O(1) for practical n, since the state cycles in at most 2^6 = 64 steps.
  • 🧺 Space complexity: O(1) for the state map (bounded by 64 states).