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

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Graph traversal

Mathematics

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

Solutions:
class Solution:

	def flipLights(self, n, m):
		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):
		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]:
			tmp = array.copy()
			if not op:
				res.append(tmp)
			else:
				for i in op:
					tmp = self.operate(i, tmp)
				if not tmp in res:
					res.append(tmp)
		return len(res)


class Solution:

	def flipLights(self, n, m):
		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):
		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(object):

	def flipLights(self, n, m):
		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(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)))
		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)