There is a room with n lights which are turned on initially and 4 buttons on the wall. After performing exactly m unknown operations towards buttons, you need to return how many different kinds of status of the n lights could be.



Suppose n lights are labeled as number [1, 2, 3 ..., n], function of these 4 buttons are given below:


Flip all the lights.
Flip lights with even numbers.
Flip lights with odd numbers.
Flip lights with (3k + 1) numbers, k = 0, 1, 2, ...




Example 1:

Input: n = 1, m = 1.
Output: 2
Explanation: Status can be: [on], [off]




Example 2:

Input: n = 2, m = 1.
Output: 3
Explanation: Status can be: [on, off], [off, on], [off, off]




Example 3:

Input: n = 3, m = 1.
Output: 4
Explanation: Status can be: [off, on, off], [on, off, on], [off, off, off], [off, on, on].



Note:
n and m both fit in range [0, 1000].

Difficulty: interview

Starter code:

class Solution:
    def flipLights(self, n: int, m: int) -> int:
        

Solutions:
class Solution:
     def flipLights(self, n, m):
         """
         :type n: int
         :type m: int
         :rtype: int
         """
         states = set()
         for op_odd in [0, 1]:
             for op_even in [0, 1]:
                 for op_third in [0, 1]:
                     op_all = m - op_odd - op_even - op_third
                     if op_all >= 0:
                         one = (op_odd + op_all + op_third) % 2
                         two = (op_even + op_all) % 2
                         three = op_odd % 2
                         four = (op_even + op_all + op_third) % 2
                         states.add((one, two, three, four)[:n])
 
         return len(states)


class Solution:
     def flipLights(self, n, m):
         """
         :type n: int
         :type m: int
         :rtype: int
         """
         if m == 0:
             return 1
         lights = [True] * min(n, 3)
         if m > 4:
             if m & 1:
                 m = 3
             else:
                 m = 4
         return self.final(m, lights)
         
     def operate(self, num, array):
         if num == 1:
             array = [not i for i in array]
         elif num == 2:
             for i in range(len(array)):
                 if i & 1:
                     array[i] = not array[i]
         elif num == 3:
             for i in range(len(array)):
                 if not i & 1:
                     array[i] = not array[i]
         elif num == 4:
             for i in range(len(array)):
                 if i%3 == 0:
                     array[i] = not array[i]
         return array
 
     def final(self, num, array):
         ops = [[[1] ,[2], [3], [4]],
                [[], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]],
                [[1] ,[2], [3], [4], [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]],
                [[], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4], [1, 2, 3, 4]]]
         res = []
         for op in ops[num-1]:
             #print(op)
             tmp = array.copy()
             if not op:
                 res.append(tmp)
                 #print('  not op')
             else:
                 #print('  op')
                 for i in op:
                     tmp = self.operate(i, tmp)
                 #print(' ', tmp)
                 if not tmp in res:
                     res.append(tmp)
         return len(res)


class Solution:
     def flipLights(self, n, m):
         """
         :type n: int
         :type m: int
         :rtype: int
         """
         n = min(n, 3)
         if n == 0: return 0
         if n == 1: return 2 if m > 0 else 1
         if n == 2: 
             if m == 0: return 1
             elif m == 1: return 3
             else: return 4
         if n == 3:
             if m == 0: return 1
             elif m == 1: return 4
             elif m == 2: return 7
             else: return 8
         
         
         
         


class Solution:
     def flipLights(self, n, m):
         """
         :type n: int
         :type m: int
         :rtype: int
         """
         if n==0:
             return 0
         if m==0:
             return 1
         if n==1:
             return 2
         if n==2:
             if m>=2:
                 return 4
             if m==1:
                 return 3
         if n>=3:
             if m>=3:
                 return 8
             if m==2:
                 return 7
             if m==1:
                 return 4

class Solution:
     def flipLights(self, n, m):
         """
         :type n: int
         :type m: int
         :rtype: int
         """
         if m == 0:
             return 1
         lights = [True] * n
         if m > 4:
             if m & 1:
                 m = 3
             else:
                 m = 4
         return self.final(m, lights)
         
     def operate(self, num, array):
         if num == 1:
             array = [not i for i in array]
         elif num == 2:
             for i in range(len(array)):
                 if i & 1:
                     array[i] = not array[i]
         elif num == 3:
             for i in range(len(array)):
                 if not i & 1:
                     array[i] = not array[i]
         elif num == 4:
             for i in range(len(array)):
                 if i%3 == 0:
                     array[i] = not array[i]
         return array
 
     def final(self, num, array):
         ops = [[[1] ,[2], [3], [4]],
                [[], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]],
                [[1] ,[2], [3], [4], [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]],
                [[], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4], [1, 2, 3, 4]]]
         res = []
         for op in ops[num-1]:
             #print(op)
             tmp = array.copy()
             if not op:
                 res.append(tmp)
                 #print('  not op')
             else:
                 #print('  op')
                 for i in op:
                     tmp = self.operate(i, tmp)
                 #print(' ', tmp)
                 if not tmp in res:
                     res.append(tmp)
         return len(res)


class Solution(object):
     def flipLights(self, n, m):
         """
         :type n: int
         :type m: int
         :rtype: int
         """
         if not n: return 0
         n,b=min(6,n),set()
         b.add(tuple([1]*n))
         for j in range(m):
             c=set()
             for x in b:
                 for t in tuple([(x[i]+1)%2 for i in range(n)]),tuple([x[i] if i%2==0 else (x[i]+1)%2 for i in range(n)]),tuple([(x[i]+1)%2 if i%2==0 else x[i] for i in range(n)]),tuple([(x[i]+1)%2 if i%3==0 else x[i] for i in range(n)]):
                     if t not in c:
                         c.add(t)
             b=c
             if len(b)==8: return 8
         return len(b)

class Solution:
     def flipLights(self, n, m):
         """
         :type n: int
         :type m: int
         :rtype: int
         """
         if n == 0:
             return 0
         if m == 0:
             return 1
         if n == 1:
             return 2
         if n == 2 and m ==1:
             return 3
         if n == 2:
             return 4
         if m == 1:
             return 4
         if m == 2:
             return 7
         return 8
         


class Solution(object):
 	def flipLights(self, lightNum, performTime):
 		if(lightNum == 0):
 			return(0)
 
 		if(performTime == 0):
 			return(1)
 
 		if(lightNum == 1):
 			return(2)
 
 		statuNumToStatu = dict()
 		statuNumToStatu[0] = (False,)*lightNum
 		statuNumToStatu[1] = (True,)*lightNum
 		statuNumToStatu[2] = tuple(True if(i%2 == 0) else False for i in range(1,lightNum+1))
 		statuNumToStatu[3] = tuple(True if(i%2 == 1) else False for i in range(1,lightNum+1))
 		statuNumToStatu[4] = tuple(True if(i%3 == 1) else False for i in range(1,lightNum+1))
 		statuNumToStatu[4] = tuple(True if(i%3 == 1) else False for i in range(1,lightNum+1))
 		statuNumToStatu[(1,4)] = tuple(True if(i%3 != 1) else False for i in range(1,lightNum+1))
 		statuNumToStatu[(2,4)] = tuple(True if((i%2 == 0)^(i%3 == 1)) else False for i in range(1,lightNum+1))
 		statuNumToStatu[(3,4)] = tuple(True if((i%2 == 1)^(i%3 == 1)) else False for i in range(1,lightNum+1))
 
 		# for key in statuNumToStatu:
 			# print(key,statuNumToStatu[key])
 
 		statuNumToNextStatuNums = {
 			0:[1,2,3,4],
 			1:[0,2,3,(1,4)],
 			2:[0,1,3,(2,4)],
 			3:[0,1,2,(3,4)],
 			4:[0,(1,4),(2,4),(3,4)],
 			(1,4):[1,4,(2,4),(3,4)],
 			(2,4):[2,4,(1,4),(3,4)],
 			(3,4):[3,4,(1,4),(2,4)],
 		}
 
 		prevStatuNums = {0}
 		for eachTime in range(performTime):
 			nextStatuNums = set()
 			for eachStatuNum in prevStatuNums:
 				for eachNextStatu in statuNumToNextStatuNums[eachStatuNum]:
 					nextStatuNums.add(eachNextStatu)
 
 			prevStatuNums = nextStatuNums
 
 		allStatus = set()
 		for eachStatuNum in prevStatuNums:
 			allStatus.add(statuNumToStatu[eachStatuNum])
 
 		return(len(allStatus))

class Solution(object):
     def flipLights(self, n, m):
         """
         :type n: int
         :type m: int
         :rtype: int
         """
         if not n: return 0
         n,b=min(6,n),set()
         b.add(tuple([1]*n))
         for j in range(m):
             c=set()
             for x in b:
                 for t in tuple([(x[i]+1)%2 for i in range(n)]),tuple([x[i] if i%2==0 else (x[i]+1)%2 for i in range(n)]),tuple([(x[i]+1)%2 if i%2==0 else x[i] for i in range(n)]),tuple([(x[i]+1)%2 if i%3==0 else x[i] for i in range(n)]):
                     if t not in c:
                         c.add(t)
             b=c
             if len(b)==8: return 8
         return len(b)