We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Prison Cells After N Days

Number: 994

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given an 8-cell prison, each cell is either occupied (1) or vacant (0). Each day, the cell states are updated: a cell becomes occupied if its two adjacent neighbors are both occupied or both vacant; otherwise, it becomes vacant. Note that because the first and last cells have only one adjacent neighbor, they will always become vacant on the next day. Given an initial state and a large number N representing days, return the prison state after N days.

Key Insights

  • The first and last cells will always become 0 after the first update.
  • Because there are a finite number of states (2^6 possible configurations for cells 1 to 6), the states will eventually repeat, forming a cycle.
  • Using cycle detection, we can reduce the effective number of days to simulate by taking N modulo the cycle length.
  • Simulation of each day is straightforward using state transformation based on neighbor comparison.

Space and Time Complexity

Time Complexity: O(2^6) in worst case (i.e. constant time, as cycle length ≤ 64). Space Complexity: O(2^6) to store seen states (also constant space).

Solution

The idea is to simulate the state transformation day by day until we notice a repetition in states. Once we detect a cycle, we know that further transformations will repeat the earlier states in a loop. We calculate the remaining number of days after accounting for full cycles (by taking modulo with the cycle length). After that, we perform simulation for the remaining days only.

We use a dictionary (or map) to store previously seen states mapped to the remaining days at that moment. When we see a state that has been seen before, we calculate the cycle length. With that, we can speed up the simulation by reducing N (the number of days left) using modulo arithmetic, then simulate only the leftover days.

The transformation for a day uses an auxiliary array where for each cell (except the first and last) the new value is set to 1 if the immediate neighbors have the same value, or 0 otherwise.

Code Solutions

# Python solution with detailed comments

def prisonAfterNDays(cells, n):
    # Dictionary to store seen states.
    # Maps state tuple to the remaining day count (n) when it was seen.
    seen = {}
    
    while n > 0:
        # Convert list to tuple for hashability.
        state_tuple = tuple(cells)
        if state_tuple in seen:
            # Cycle detected: compute the cycle length.
            cycle_length = seen[state_tuple] - n
            # Reduce n by using modulo of the cycle length.
            n %= cycle_length
        # Record the state along with the current remaining day count.
        seen[state_tuple] = n
        
        # If there are still days left, simulate one day.
        if n >= 1:
            n -= 1
            # Compute next state.
            cells = nextDay(cells)
    return cells

def nextDay(cells):
    # New state initialization (first and last cell become 0).
    new_cells = [0] * 8
    # Update cells 1 to 6 based on the two neighbors.
    for i in range(1, 7):
        # Cell becomes 1 if both neighbors are the same, 0 otherwise.
        new_cells[i] = 1 if cells[i-1] == cells[i+1] else 0
    return new_cells

# Example usage:
if __name__ == "__main__":
    cells_example = [0,1,0,1,1,0,0,1]
    n_days = 7
    result = prisonAfterNDays(cells_example, n_days)
    print(result)  # Expected Output: [0,0,1,1,0,0,0,0]
← Back to All Questions