There are $8$ prison cells arranged in a row, where each cell is represented by either $1$ if it is occupied or $0$ if it is vacant.

Every day, the state of all cells changes simultaneously based on these rules:

• A cell becomes occupied with a value of $1$ if both of its adjacent neighbors are occupied or both are vacant.

• Otherwise, the cell becomes vacant with a value of $0$.

Since the first and last cells in the row lack two adjacent neighbors, they cannot satisfy the condition and become vacant with a value of $0$ on each subsequent day.

Given an integer array cells representing the initial state of the prison and an integer n, return the state of the prison cells after n days.

Constraints:

• cells.length is equal to $8$

• cells[i] is either $0$ or $1$

• $1 \le n \le 10^9$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.