First of all, we can just discuss the case that
n = 1,2,3,4,5,6, because the lights repeat the pattern of first 6 bulbs. Remarkably, the 5th and 6th bulb is the same as 4th and 3th respectively, so we just need to discuss the case
n = 1,2,3,4. When
n>4, it is the same as
If you are familiar with group theory, this question is quite simple. We now have four operations
A (flip All),
E (flip Even),
O (flip Odd),
K (flip 3k+1). Here we denote identical operation (the operation that changes nothing) with
I. It's obvious that all operations are commutative, the order in which they are performed does not matter. Additionally, we have some other basic rules here, such as perform the same operation twice is equal to do nothing, and flipping all and then flipping even is equal to just flipping Odd. Formally, these rule can be written as
AA=EE=OO=KK=I # two same operation is equal to Identical operation AE=O # flipping all and even is equal to flipping odd AO=E # flipping all and odd is equal to flipping even OE=A # flipping odd and even is equal to flipping all
In this trivial case, the answer is always 2.
In this case, the operation K is equal to operation O, so we actually have three operations
A, O, E.
m=1, three status by performing
A, O, E. We can draw a table to count the status. The table below shows where can we reach from the identical operation (the initial status is equal to having performed an identical operation).
___|_A___O___E_ I | A O E
m=2, we draw table below. In the case
m=1, we can reach
A, O, E, after performing one more operation we can reach
A, O, E, I, four status.
___|_A___O___E_ A | I E O O | E I A E | O A I
m=3, we show go one operation far from
m=2. Again, we can reach four status
A, O, E, I.
___|_A___O___E_ A | I E O O | E I A E | O A I I | A O E
m>3, the table will be the same as
Now we have four distinct operations
A, O, E, K.
m=1, four kinds of status,
A, O, E, K
___|_A__O__E__K__ I | A O E K
m=2, we have 7 kinds of status,
I, A, O, E, AK, EK, OK. Here,
AK means perform operation
K in order.
EK, OK is the same.
___|_A___O___E___K_ A | I E O AK O | E I A OK E | O A I EK K | AK OK EK I
m=3, we have 8 kinds of status,
A, O, E, K, I, AK, OK, EK.
___|_A___O___E___K_ A | I E O AK O | E I A OK E | O A I EK I | A O E K - - - - - - - - - - # Add this line to make it more readable AK | K EK OK A OK | EK K AK A EK | OK AK K A
m>3, the table will be above one with an extra row. But this does not introduce new status. So it is still 8 kinds of status.
___|_A___O___E___K_ K | AK OK EK I
The reuslts forms this table:
n\m_0_1_2_3_... 1| 1 2 2 2 ... 2| 1 3 4 4 ... 3| 1 4 7 8 ... 4| 1 4 7 8 ... .| . . . . .| . . . .
class Solution(object): def flipLights(self, n, m): """ :type n: int :type m: int :rtype: int """ if m == 0: return 1 elif n == 1: return 2 elif n == 2: return 3 if m<2 else 4 else: if m == 1: return 4 elif m == 2: return 7 else: return 8