672. Bulb Switcher II


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:

  1. Flip all the lights.
  2. Flip lights with even numbers.
  3. Flip lights with odd numbers.
  4. 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].


Approach #1: Reduce Search Space [Accepted]

Intuition

As the search space is very large ( states of lights, naively operation sequences), let us try to reduce it.

The first 6 lights uniquely determine the rest of the lights. This is because every operation that modifies the -th light also modifies the -th light.

Also, operations commute: doing operation A followed by B is the same as doing operation B followed by A. So we can assume we do all the operations in order.

Finally, doing the same operation twice in a row is the same as doing nothing. So we only need to consider whether each operation was done 0 or 1 times.

Algorithm

Say we do the -th operation times. Let's first figure out what sets of residues are possible: that is, what sets ( ) are possible.

Because and , if , or if , it isn't possible. Otherwise, it is possible by a simple construction: do the operations specified by , then do operation number 1 with the even number of operations you have left.

For each possible set of residues, let's simulate and remember what the first 6 lights will look like, storing it in a Set structure seen. At the end, we'll return the size of this set.

In Java, we make use of bit manipulations to manage the state of lights, where in Python we simulate it directly.

Complexity Analysis

  • Time Complexity: . Our checks are bounded by a constant.

  • Space Complexity: , the size of the data structures used.

Approach #2: Mathematical [Accepted]

Intuition and Algorithm

As before, the first 6 lights uniquely determine the rest of the lights. This is because every operation that modifies the -th light also modifies the -th light, so the -th light is always equal to the -th light.

Actually, the first 3 lights uniquely determine the rest of the sequence, as shown by the table below for performing the operations a, b, c, d:

  • 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
  • Light 6 = Light 2

The above justifies taking without loss of generality. The rest is now casework.

Let's denote the state of lights by the tuple . The transitions are to XOR by or .

When , all the lights are on, and there is only one state . The answer in this case is always 1.

When , we could get states , , , or . The answer in this case is either for respectively.

When , we can manually check that we can get 7 states: all of them except for . The answer in this case is either for respectively.

When , we can get all 8 states. The answer in this case is either for respectively.

Complexity Analysis

  • Time and Space Complexity: . The entire program uses constants.

Analysis written by: @awice.

Submit Solution