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 $i^{th}$ 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 1:

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$

From: LeetCode
Link: 957. Prison Cells After N Days

Solution:

Ideas:

• There are only 256 possible states because each of the 8 cells is either 0 or 1.

• After some days, the states will repeat, forming a cycle.

• Simulate day by day while recording each state.

• When a repeated state is found, cycle detected → stop simulation.

• Use math:

  • Skip directly to the final day using (n - cycleStart) % cycleLength.

• Return the state corresponding to the computed final index.

Code:

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
static void nextDay(int *cur, int cellsSize, int *next) {
    // First and last cell always become 0 (no two neighbors)
    next[0] = 0;
    next[cellsSize - 1] = 0;
    for (int i = 1; i < cellsSize - 1; i++) {
        // If neighbors are both 0 or both 1 -> occupied (1), else vacant (0)
        if (cur[i - 1] == cur[i + 1]) {
            next[i] = 1;
        } else {
            next[i] = 0;
        }
    }
}

int* prisonAfterNDays(int* cells, int cellsSize, int n, int* returnSize) {
    *returnSize = cellsSize;
    if (cellsSize == 0 || n == 0) {
        int *res = (int*)malloc(cellsSize * sizeof(int));
        memcpy(res, cells, cellsSize * sizeof(int));
        return res;
    }

    // There are at most 2^8 = 256 possible states.
    // states[d][i] = state of cell i on day d.
    const int MAX_STATES = 256;
    int states[MAX_STATES][8];  // cellsSize is 8 per problem constraints

    // Day 0: initial state
    memcpy(states[0], cells, cellsSize * sizeof(int));

    int cycleStart = -1;
    int cycleLen = 0;
    int totalDaysComputed = 0;

    for (int day = 1; day <= n && day < MAX_STATES; day++) {
        // Compute next state from previous day
        nextDay(states[day - 1], cellsSize, states[day]);
        totalDaysComputed = day;

        // Check if this state has appeared before (cycle detection)
        for (int k = 0; k < day; k++) {
            if (memcmp(states[k], states[day], cellsSize * sizeof(int)) == 0) {
                cycleStart = k;
                cycleLen = day - k;
                break;
            }
        }
        if (cycleStart != -1) {
            break;
        }
    }

    int resultIndex;

    if (cycleStart == -1 || n <= totalDaysComputed) {
        // Either no cycle detected (within n) or we simulated exactly n days
        resultIndex = (n <= totalDaysComputed) ? n : totalDaysComputed;
    } else {
        // We have a cycle: states[cycleStart .. cycleStart+cycleLen-1]
        if (n <= cycleStart) {
            resultIndex = n;
        } else {
            int rem = (n - cycleStart) % cycleLen;
            resultIndex = cycleStart + rem;
        }
    }

    int *res = (int*)malloc(cellsSize * sizeof(int));
    memcpy(res, states[resultIndex], cellsSize * sizeof(int));
    return res;
}