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

&nbsp;
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]


&nbsp;
Constraints:


	cells.length == 8
	cells[i]&nbsp;is either 0 or 1.
	1 &lt;= n &lt;= 109


class Solution:
    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:
        patternMatch=defaultdict(int) # pattern match
        totalPrisons=8 # totalPrisons
        cells= [ str(c) for c in (cells)] # into char type
        for d in range(1,n+1):
            tempCell=[]
            tempCell.append('0') # left corner case
            for c in range(1,totalPrisons-1):
                if (cells[c-1]=='1' and cells[c+1]=='1') or (cells[c-1]=='0' and cells[c+1]=='0'):
                    tempCell.append('1') # insert 1 if first condition met
                else:
                    tempCell.append('0') # otherwise 0
            tempCell.append('0') # right corner case
            cells=tempCell # update cells
            pattern= ''.join(tempCell) # insert pattern in hashtable
            if pattern in patternMatch: # if there is a match
                day=patternMatch[pattern]
                remainder= (n%(d-1))-1 # take modulo
                match= list(patternMatch.keys())[remainder] # find key
                return [ int(m) for m in match] # return
            patternMatch[pattern]=d # assign day
        return [ int(c) for c in (cells)] # return
class Solution {
    public int[] prisonAfterNDays(int[] cells, int n) {
        // # Since we have 6 cells moving cells (two wil remain unchaged at anytime) 
        // # the cycle will restart after 14 iteration
        // # 1- The number of days if smaller than 14 -> you brute force O(13)
        // # 2- The number is bigger than 14
        // #                       - You do a first round of 14 iteration
        // #                       - Than you do a second round of n%14 iteration
        // #                       ===> O(27)
        
        n = n % 14 == 0 ? 14 : n%14;
        int temp[] = new int[cells.length];
        
        while(n-- > 0)
        {
            for(int i=1; i <cells.length- 1; i++)
            {
              temp[i] = cells[i-1] == cells[i+1]? 1: 0;
            }
            cells = temp.clone();
        }

        return cells;
    }
}
class Solution {
public:
    vector<int> prisonAfterNDays(vector<int>& cells, int n) {
        //since there are only a 2**6 number of states and n can go to 10**9
        //this means that there is bound to be repetition of states
        int state=0;
        //making the initial state bitmask
        for(int i=0;i<cells.size();i++){
            if(cells[i]){
                state^=(1<<(7-i));
            }
        }
        //this array stores the various states encountered
        vector<int>seen;
        while(n--){
            int next=0;
            //transitioning to the next state
            for(int pos=6;pos>0;pos--){
                int right=pos+1,left=pos-1;
                if(((state>>right)&1)==((state>>left)&1)){
                    next|=(1<<pos);
                }
            }
            //if the next state is equal to the initial state, this means that we have
            //found the cycle. Let the length of the cycle be l=seen.size(). Therefore 
            //in the remaining n days, n/l of those will have no effect on the 
            //prison configuration. This means we can return the configuration of the 
            //n%l day.
            if(seen.size() and seen[0]==next){
                int cnt=seen.size();
                state=seen[n%cnt];
                break;
            } else {
                seen.push_back(next);
                state=next;
            }
        }
        //translating the prison state from the bitmask to an array.
        vector<int>ans(cells.size(),0);
        for(int i=0;i<8;i++){
            if((state>>i)&1){
                ans[7-i]=1;
            }
        }
        return ans;
    }
};
/**
 * @param {number[]} cells
 * @param {number} n
 * @return {number[]}
 */

var prisonAfterNDays = function(cells, n) {
    const set = new Set()
    let cycleDuration = 0
    
    while(n--) {
        const nextCells = getNextCells(cells)

        // 1. Get cycle length
        if(!set.has(String(nextCells))){
            set.add(String(nextCells))
            cycleDuration++
            cells = nextCells
            
        } else {
            // 2. Use cycle length to iterate once more to get to correct order
            let remainderToMove = n%cycleDuration
            while(remainderToMove >= 0) {
                remainderToMove--
                cells = getNextCells(cells)
            }
            break
        }        
        
    }
    
    return cells
};

function getNextCells(cells) {
    let temp = [...cells]
    for(let i = 0; i < 8; i++) {
        if(i>0 && i < 7 && cells[i-1] === cells[i+1]) {
            temp[i] = 1
        } else {
            temp[i] = 0
        }
    }

    return temp
}

// 0
// 1
// 2
// n

// 1 000 000 % n 
Prison Cells After N Days