672. Bulb Switcher II

Description

Here

Intuition

1. 初步观察可得，如果update了 x light，那么 (x+6) light.

2. 进一步观察可得

   1. Assume:

      1. a denotes Flip all the lights.
      2. b denotes Flip lights with even numbers.
      3. c denotes Flip lights with odd numbers.
      4. D denotes Flip lights with (3k + 1) numbers, k = 0, 1, 2, ...

   2. Light 1 = 1 + a + c + d

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

   那么可以发现，

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

3. 所以，我们可以用头3个灯泡来表示所有的灯泡状态

   1. m == 1，所以有 a,b, c,d四种操作

      1 1 1 (Orignal)
      0 0 0 (a)
      1 0 1 (b)
      0 1 0 (c)
      0 1 1 (d)
      

   2. m == 2

      1 1 1 (Orignal)
      1 1 1 (aa -> null)
      0 1 0 (ab -> c)
      1 0 1 (ac -> b)
      1 0 0 (ad -> null)
      0 1 0 (ba -> ab)
      1 1 1 (bb -> null)
      0 0 0 (bc -> a)
      0 0 1 (bd -> null)
      1 1 0 (cd -> null)
      

      1. n == 1, return 2
      2. n == 2, 11, 00, 01, 10, return 4
      3. n == 3, 111, 110, 101, 100, 010, 001, 000, return 7

   3. m == 3

  ```java
  1 1 1 (Orignal)
  0 0 0 (aaa -> a)
  1 0 1 (aab -> b)
  0 1 0 (aac -> c)
  0 0 1 (aad -> d)
  1 1 1 (abc -> null)
  1 1 0 (abd -> cd)
  0 0 1 (acd -> bd)
  1 0 0 (bcd -> ad)
  ```
  1. `n == 1`, `return 2`
  1. `n == 2`, `11`, `00`, `01`, `10`, `return 4`
  1. `n == 3`, `111`, `110`, `101`, `100`, `011`, `010`, `001`, `000`, `return 8`

Solution

solution