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 是多少，然後再經過一點運算就可以得到答案了

---

作業

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