Python O(1), with detailed analysis.


  • 1
    L

    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 n=4.

    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
    

    When n=1

    In this trivial case, the answer is always 2.

    When n=2

    In this case, the operation K is equal to operation O, so we actually have three operations A, O, E.
    If 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 
    

    If 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 
    

    if 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
    

    If m>3, the table will be the same as m=3.

    When n>=3

    Now we have four distinct operations A, O, E, K.
    If m=1, four kinds of status, A, O, E, K

    ___|_A__O__E__K__
     I | A  O  E  K 
    

    if m=2, we have 7 kinds of status, I, A, O, E, AK, EK, OK. Here, AK means perform operation A and 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
    

    if 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
    

    if 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
    

    Summary

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

    Python Code

    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
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.