###### tags: `957 Prison Cells After N Days`
# 957 Prison Cells After N Days 筆記

## 題目：

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

**Constraints:**

- `cells.length == 8`
- `cells[i]` is either `0` or `1`.
- $1 <= n <= 10^9$

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 = 7
Output: [0,0,1,1,1,1,1,0]
Explanation: The following table summarizes the state of the prison on each day:
Days 0: [1, 0, 0, 1, 0, 0, 1, 0]
Days 1: [0, 0, 0, 1, 0, 0, 1, 0]
Days 2: [0, 1, 0, 1, 0, 0, 1, 0]
Days 3: [0, 1, 1, 1, 0, 0, 1, 0]
Days 4: [0, 0, 1, 0, 0, 0, 1, 0]
Days 5: [0, 0, 1, 0, 1, 0, 1, 0]
Days 6: [0, 0, 1, 1, 1, 1, 1, 0]
Days 7: [0, 0, 0, 1, 1, 1, 0, 0]

## 觀察：

Day 2, 4 ,6 的 index 1, 3, 5 會是一樣的

Day 1, 3, 5, 7 的 index 2, 4, 6 會是一樣的

但是到了 Example 2 就不適用了，試著把 n 拉大一點試試看

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

Days 00: [0, 1, 0, 1, 1, 0, 0, 1]
Days 01: [0, 1, 1, 0, 0, 0, 0, 0]
Days 02: [0, 0, 0, 0, 1, 1, 1, 0]
Days 03: [0, 1, 1, 0, 0, 1, 0, 0]
Days 04: [0, 0, 0, 0, 0, 1, 0, 0]
Days 05: [0, 1, 1, 1, 0, 1, 0, 0]
Days 06: [0, 0, 1, 0, 1, 1, 0, 0]
Days 07: [0, 0, 1, 1, 0, 0, 0, 0]
Days 08: [0, 0, 0, 0, 0, 1, 1, 0]
Days 09: [0, 1, 1, 1, 0, 0, 0, 0]
Days 10: [0, 0, 1, 0, 0, 1, 1, 0]
Days 11: [0, 0, 1, 0, 0, 0, 0, 0]
Days 12: [0, 0, 1, 0, 1, 1, 1, 0]
Days 13: [0, 0, 1, 1, 0, 1, 0, 0]
Days 14: [0, 0, 0, 0, 1, 1, 0, 0]
Days 15: [0, 1, 1, 0, 0, 0, 0, 0]
Days 16: [0, 0, 0, 0, 1, 1, 1, 0]
Days 17: [0, 1, 1, 0, 0, 1, 0, 0]
Days 18: [0, 0, 0, 0, 0, 1, 0, 0]
Days 19: [0, 1, 1, 1, 0, 1, 0, 0]
Days 20: [0, 0, 1, 0, 1, 1, 0, 0]
Days 21: [0, 0, 1, 1, 0, 0, 0, 0]
Days 22: [0, 0, 0, 0, 0, 1, 1, 0]
Days 23: [0, 1, 1, 1, 0, 0, 0, 0]
Days 24: [0, 0, 1, 0, 0, 1, 1, 0]
Days 25: [0, 0, 1, 0, 0, 0, 0, 0]
Days 26: [0, 0, 1, 0, 1, 1, 1, 0]
Days 27: [0, 0, 1, 1, 0, 1, 0, 0]
Days 28: [0, 0, 0, 0, 1, 1, 0, 0]
Days 29: [0, 1, 1, 0, 0, 0, 0, 0]
Days 30: [0, 0, 0, 0, 1, 1, 1, 0]

發現 Days 01 跟 Days 15 會重複，之後就會一直重複這個循環

再看另一個範例

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

Days 00: [1, 0, 0, 1, 0, 0, 1, 0]
Days 01: [0, 0, 0, 1, 0, 0, 1, 0]
Days 02: [0, 1, 0, 1, 0, 0, 1, 0]
Days 03: [0, 1, 1, 1, 0, 0, 1, 0]
Days 04: [0, 0, 1, 0, 0, 0, 1, 0]
Days 05: [0, 0, 1, 0, 1, 0, 1, 0]
Days 06: [0, 0, 1, 1, 1, 1, 1, 0]
Days 07: [0, 0, 0, 1, 1, 1, 0, 0]
Days 08: [0, 1, 0, 0, 1, 0, 0, 0]
Days 09: [0, 1, 0, 0, 1, 0, 1, 0]
Days 10: [0, 1, 0, 0, 1, 1, 1, 0]
Days 11: [0, 1, 0, 0, 0, 1, 0, 0]
Days 12: [0, 1, 0, 1, 0, 1, 0, 0]
Days 13: [0, 1, 1, 1, 1, 1, 0, 0]
Days 14: [0, 0, 1, 1, 1, 0, 0, 0]
Days 15: [0, 0, 0, 1, 0, 0, 1, 0]
Days 16: [0, 1, 0, 1, 0, 0, 1, 0]
Days 17: [0, 1, 1, 1, 0, 0, 1, 0]
Days 18: [0, 0, 1, 0, 0, 0, 1, 0]
Days 19: [0, 0, 1, 0, 1, 0, 1, 0]
Days 20: [0, 0, 1, 1, 1, 1, 1, 0]
Days 21: [0, 0, 0, 1, 1, 1, 0, 0]
Days 22: [0, 1, 0, 0, 1, 0, 0, 0]
Days 23: [0, 1, 0, 0, 1, 0, 1, 0]
Days 24: [0, 1, 0, 0, 1, 1, 1, 0]
Days 25: [0, 1, 0, 0, 0, 1, 0, 0]
Days 26: [0, 1, 0, 1, 0, 1, 0, 0]
Days 27: [0, 1, 1, 1, 1, 1, 0, 0]
Days 28: [0, 0, 1, 1, 1, 0, 0, 0]
Days 29: [0, 0, 0, 1, 0, 0, 1, 0]
Days 30: [0, 1, 0, 1, 0, 0, 1, 0]

發現 Days 01 也會在 Days 15 重複

雖然不知道原因，到觀察到了規律就可以解題了

這裡還有一個額外要注意的點是，如果頭尾在一開始都是 0 的時候就要從 Days 00 開始觀察

題目裡的 $n=10^9$ 顯然不能夠用暴力運算，那會超時

發現這個規律就可以看 n % 14 是多少，然後再經過一點運算就可以得到答案了

---
[作業](https://github.com/GametreeRoger/LeetCode/blob/main/LeetCode957.playground/Contents.swift)

## Alex 補充資料
1. Input Size
https://www.youtube.com/watch?v=eG99FDBeuJo
2. XOR
https://leetcode.com/problems/single-number/
3. Why does this pattern repeat after 14 cycles instead of 256, can you give a proof?
https://math.stackexchange.com/questions/3311568/why-does-this-pattern-repeat-after-14-cycles-instead-of-256-can-you-give-a-proo