 # Prison Cells After N Days

## Problem Statement

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.)

We describe the current state of the prison in the following way: `cells[i] == 1` if the `i`-th cell is occupied, else `cells[i] == 0`.

Given the initial state of the prison, return the state of the prison after `N` days (and `N` such changes described above.)

## Sample Test Case

```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]```

## Problem Solution

If no of days ie N is small then it is easy to loop through the array and change the values according to given constraint. But we need to optimize our solution for large value of N .

As, after first iteration first and last cell will be fix with 0 so we are left with only 6 cells – and we have 2 choices 0 or 1 so how many total combinations we have? = `2^6` = `64` with this we can confirm that patterns will definitely repeat.
Now how to optimize? we save the states in a Set data structure and check if it not already the contains state before adding and also keep a len variable to track the len. If a particular state is already present in the set this means we have found the repetition cycle.

Once we found the cycle we will return N % len day state.

Once we have the cycle with us we can skip the unnecessary iteration and directly jump to the next state.

## Complexity Analysis

Time Complexity : O(N) as we are looping through all the days(in worst case).

Space Complexity: O(N) since we are storing the states in a Set.

## Code Implementation

```#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> prisonAfterNDays(vector<int>& cells, int N) {
map <int, vector <int> > m;
if(N == 0) return cells;
set <vector <int> > visited;
visited.insert(cells);
for(int i = 1; i<=14 ; i++ ){
vector <int> temp(8);
for(int j = 1; j < 7; j++){
if(cells[j - 1] ^ cells[j + 1] == 0){
temp[j] = 1;
}
}
cells = temp;
m[i] = temp;
visited.insert(temp);
}
return m[N % 14 == 0? 14 : N % 14];
}
};
main(){
vector<int> v1 = {0,1,0,1,1,0,0,1};
Solution ob;
print_vector(ob.prisonAfterNDays(v1, 7));
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]