Skip to content

957. Prison Cells After N Days

There are 8 prison cells in a row and each cell is either occupied or vacant.

occupied: 占用

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.

0 1 0

1 1 1

  • Otherwise, it becomes vacant.

0 0 1

1 0 1

Note that because the prison is a row, the first and the last cells in the row can't have two adjacent neighbors.

0 ... 0

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

Solution:

index 0 1 2 3 4 5 6 7
0 1 0 1 1 0 0 1
n=1 0 1 1 0 0 0 0 0 
class Solution {
    public int[] prisonAfterNDays(int[] cells, int n) {
        for (int i = 0; i < n; i++){
            cells = nextDay(cells);
        }

        return cells;
    }

    private int[] nextDay(int[] cells){
        int[] tmp = new int[cells.length];
        for (int i = 1; i < cells.length - 1; i++){
            if ((cells[i - 1] == 0 && cells[i + 1] == 0) || (cells[i-1] == 1 && cells[i + 1] == 1)){
                // cells[i - 1] == cells[i + 1]
                tmp[i] = 1;
            }else{
                tmp[i] = 0;
            }
        }

        return tmp;
    }
}
// Case 1 pass
// TLM

class Solution {
    public int[] prisonAfterNDays(int[] cells, int n) {
        Set<String> set = new HashSet<>();
        boolean hasCycle = false;
        int count = 0;
        for (int i = 0; i < n; i++){
            int[] next = nextDay(cells);
            String s = Arrays.toString(next);
            if (!set.contains(s)){
                set.add(s);
                count++;
            }else{
                hasCycle = true;
                break;
            }
            cells = next;
        }

        if (hasCycle == true){
            n = n % count;
            for (int i = 0; i < n; i++){
                cells = nextDay(cells);
            }
        }

        return cells;
    }

    private int[] nextDay(int[] cells){
        int[] tmp = new int[cells.length];
        for (int i = 1; i < cells.length - 1; i++){
            if ((cells[i - 1] == 0 && cells[i + 1] == 0) || (cells[i-1] == 1 && cells[i + 1] == 1)){
                // cells[i - 1] == cells[i + 1]
                tmp[i] = 1;
            }else{
                tmp[i] = 0;
            }
        }

        return tmp;
    }
}

// TC: O(2^n)
// SC: O(2^n)

Reference

https://www.bilibili.com/video/BV1SE411y7vY/?spm_id_from=333.337.search-card.all.click&vd_source=73e7d2c4251a7c9000b22d21b70f5635