Mathematical Solution with Explanation


  • 1

    Firstly, we may take n = min(n, 3). The sequence of lights clearly repeats every 6, so the first 6 lights are representative of the whole sequence, as we can construct eg. the 7th light (it's equal to the 1st).

    Actually, the first 3 lights are representative of the whole sequence. If the operations are a, b, c, d; then modulo 2:

    • Light 1 = 1 + a + c + d
    • Light 2 = 1 + a + b
    • Light 3 = 1 + a + c
    • Light 4 = 1 + a + b + d
    • Light 5 = 1 + a + c
    • Light 6 = 1 + a + b

    So that (modulo 2):

    • Light 4 = (Light 1) + (Light 2) + (Light 3)
    • Light 5 = Light 3, and
    • Light 6 = Light 2.

    Now, we can do cases on m, and analyze the possible lightbulb states for n >= 3. The transitions are to XOR by (1, 1, 1), (0, 1, 0), (1, 0, 1), or (1, 0, 0).

    • If m = 0 there is only one state (1, 1, 1).
    • If m = 1 then we could get (0, 0, 0), (1, 0, 1), (0, 1, 0), (0, 1, 1).
    • If m = 2 we could get all 8 possibilities except (0, 1, 1).
    • If m = 3 we can get every possibility.

    This reduced the problem to knowing the answer for m <= 3, n <= 3. The final answer is:

    • When n == 1, the answer is 1 if m == 0, else 2.
    • When n == 2, the answer is 1 if m == 0, 3 if m == 1, else 4.
    • When n >= 3, the answer is 1 if m == 0, 4 if m == 1, 7 if m == 2, else 8.

  • 0

    @awice said in Mathematical Solution with Explanation:

    The sequence of lights clearly repeats every 6, so the first 6 lights are representative of the whole sequence, as we can construct eg. the 7th light (it's equal to the 1st)

    Hi @awice Thanks for the explanation. If possible, could you help to explain why " The sequence of lights clearly repeats every 6, so the first 6 lights are representative of the whole sequence, as we can construct eg. the 7th light (it's equal to the 1st)"? How do you figure out that lights pattern repeated every 6? Thanks!


  • 0

    @coder42 The first operation repeats every 1 light. The second and third operations repeat every 2 lights. The fourth operation repeats every 3 lights. In total, they must all repeat every lcm(1, 2, 2, 3) = 6 lights.


Log in to reply
 

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