Prison Cells After N Days LeetCode Solution

Quoestion: Click Here

Input: cells = [0,1,0,1,1,0,0,1], N = 7

Output: [0,0,1,1,0,0,0,0]

Given 1<= N <= 10^9

Approach:

If we repeat the process for atmost 10^9 times we get time limit exceeded error.

so,we need to optimize

If we Look at the above picture It is known that it's repeating after every 14 days and it is making a cycle.So we change N by N = N%14.So that no of iterations can be decreased and code runs faster.

Algorithm:

=>Update N to N % 14,if N==0 then update N = 14.

=>Loop from 1 to N

    =>Intialize a temp array of size 8

    =>Loop from 1 to 6

           =>if cells[i-1]== cells[i+1]:

                    =>add 1 to temp

           =>else:

                    =>add 0 to temp

    =>add 0 to temp at end

    => update cell = temp

=>return cell

Python Code:       

class Solution(object):
    def prisonAfterNDays(self, cells, N):
        N = N % 14
        if N==0:
            N = 14
        while N:
            lst = []
            lst.append(0)
            for i in range(1,len(cells)-1):
                if cells[i-1]== cells[i+1]:
                    lst.append(1)
                else:
                    lst.append(0)
            lst.append(0)
            cells = lst
            N-=1
        return cells  

Try Problem in LeetCode