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
0 Comments