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:
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).
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 == 8cells[i] is either 0 or 1.1 <= n <= 109In #957 Prison Cells After N Days, each day's state depends only on the previous configuration of eight cells. A key observation is that the first and last cells always become 0, meaning only the middle six cells actually change. This creates a limited number of possible states, which leads to a repeating cycle.
The common strategy is to simulate the cell transitions day by day while storing previously seen states in a hash table. Once a state repeats, a cycle is detected. Instead of simulating all N days, you can compute N % cycle_length and only simulate the remaining days. This drastically reduces the number of operations when N is very large.
An optimized implementation can represent the cells using bit manipulation, converting the 8-cell array into a bitmask for faster transitions and compact storage. The approach leverages pattern repetition to avoid unnecessary simulation.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Simulation with Hash Set (Cycle Detection) | O(min(N, 64)) | O(64) |
| Bitmask + Cycle Detection | O(min(N, 64)) | O(1) |
Techdose
This approach involves simulating each day's changes directly. Given the constraints of the problem, this can be manageable for relatively small values of 'n'. We iterate over each day, applying the rules to determine the state of each cell. Importantly, the edge cells are always vacant as they lack two neighbors. By updating the state iteratively, we can reach the final configuration after 'n' days.
Time complexity: O(1), as the complexity per cycle of states is fixed. During each cycle, we just iterate over the 8 states.
Space complexity: O(1), only a fixed array is used for state computation.
1#include <stdio.h>
2#include <string.h>
3
4void nextDay(int *cells, int *nextCells) {
5 nextCells
The C program defines a function nextDay to calculate the state of cells for the next day based on the current state using the rules provided. The prisonAfterNDays function uses this helper function to simulate day-by-day changes. The logic accommodates the cyclic nature of the problem by using n % 14 to optimize large iterations, where 14 is the length of the repeating cycle determined by observation and testing.
This alternative approach builds on recognizing patterns within the transformations. Given only 8 cells and binary states, the maximum number of possible unique states is 27 = 128. Through simulation, we can identify that the pattern cycles or repeats after at most 14 days, reducing the need to simulate all given 'n' days. By finding cycles, one can compute the state that would correspond to the final day directly, drastically minimizing operations.
Time complexity: O(128), as we explore states to identify cycles, bounded by maximum unique states of 128.
Space complexity: O(128), accommodates tracking up to 128 states.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The problem has a fixed number of cells and deterministic rules, which means the number of possible states is finite. After several transitions, a previously seen state must appear again. This repetition creates a cycle in the sequence of states.
Yes, this problem is a popular medium-level interview question. It tests understanding of arrays, simulation, hash tables, and recognizing repeating patterns or cycles in state transitions.
A hash set or hash map is commonly used to store previously seen cell states. This helps quickly detect cycles in the simulation. Some optimized solutions also use bitmasks to represent the cells efficiently.
The optimal approach uses cycle detection while simulating the cell states. Since the number of possible configurations is limited, the states eventually repeat. Once a cycle is found, you can reduce N using modulo arithmetic and simulate only the remaining days.
The C code leverages a direct approach to identify patterns using the findCycle method, where state sequences are preserved and revisited to determine recurring configurations. This understanding is then used to restrict operations to only necessary repetitions through precise cycle length determination.