https://leetcode.com/problems/prison-cells-after-n-days

Let us solve this problem by definition: we do iteration by iteration. However if N is very big, then we spend O(N) time and it can take too much time. Note, that there can be only 2^8 possible options for cells (in fact only 2^6 even, because after first step the first and the last symbols will always be zeros). It means, that afrer some number of iterations, cells start to repeat, and we found a loop.

How can we find a loop? We need to keep our positions in hash-table, so we can find loop_len. We do iteration by iteration and if we found a loop, we need to do (N - i) % loop_len more steps.

Complexity: time and memory is O(64), because the loop size will be not more than 64.

class Solution:
    def next_step(self, cells):
        res = [0] * 8
        for i in range(1,7):
            res[i] = int(cells[i-1] == cells[i+1])
        return res
    
    def prisonAfterNDays(self, cells, N):
        found_dic = {}
        for i in range(N):
            cells_str = str(cells)
            if cells_str in found_dic:
                loop_len = i - found_dic[cells_str]
                return self.prisonAfterNDays(cells, (N - i) % loop_len)
            else:
                found_dic[cells_str] = i 
                cells = self.next_step(cells) 
                
        return cells

PS there are also solutions which are using the fact that if there is a loop, it will always have length 14 (or divisor of it). However will you find this on real interview?

If you like the solution, you can upvote it on leetcode discussion section: Problem 0957