A few big names from Microsoft and Google have organized an interview question brushing group. You can add the administrator VX: SxxZs3998 to participate in the discussion and live broadcast

Problem 1.

There is a room with n turned on light bulbs and 4 buttons on the wall. After m unknown operations, you have to go back to how many different states these N bulbs could be in. Assuming that the n bulbs are numbered [1, 2, 3… n], the functions of the four buttons are as follows:

  • Reverse the status of all light bulbs (i.e. on to off, off to on)
  • Reverses the status of an even numbered bulb
  • Reverses the status of an odd-numbered bulb
  • Reverse the state of the bulb numbered 3K ^1 (k = 0, 1, 2…)
Example 1: Input: n = 1, m = 1. Output: 2 Description: The status is [on], [off] Example 2: Input: n = 2, m = 1. Output: 3: status to: [open and shut], [,], [shut, shut] example 3: input: n = 3, m = 1. Output: 4: status to: [shut, open and close], [open, close, open], [pass, pass, pass], [shut, open, open].Copy the code

2.

2.1 cognitive

Here is an analysis of all of the 6 light bulbs:

As you can clearly see from the diagram, if the number of bulbs is more than 6, that is the condition of the first 6 bulbs in the repeat cycle. Let’s start with the theoretical analysis.

2.2 Problem Solving

Since the search space is very large (2N2^N2N states of lights, 4M4^M4M sequences of operations), let’s try to reduce it.

The first six lights uniquely determine the rest of the lights. This is because every operation that modifies the XXX light modifies the (x6)(x^6)(x6) light.

So let’s simplify m

Doing AN OPERATION A followed by an operation B is the same as doing an operation B followed by an operation A, so we can assume that we do all the operations in sequence.

Finally, doing the same operation twice in a row is the same as doing nothing at all. So we just have to think about whether each operation is zero or one.

And then simplify n

The following four operations are set to a, B, C, D a. Reverse the status of all the bulbs (i.e. on to off, off to on) b. C. Reverse the state of an even-numbered bulb D. reverse the state of an odd-numbered bulb Reverse the state of the bulb numbered 3K ^1 (k = 0, 1, 2…)

Let a,b,c,da,b,c,da,b,c, da,b,c,d be the four operations that have been performed. a,! b,! c,! d! a,! b,! c,! d! a,! b,! c,! D is for four operations not performed, among which, since the first six lights uniquely determine the rest, we will simplify to 6.

Assuming n > 6, all the bulbs have been initially switched on, you can see that for all the states that the bulbs have (this section also explains why the first 6 lights determine the rest)

Light 1 = true ^ a ^ c ^ d Light 2 = true ^ a ^ b Light 3 = true ^ a ^ c Light 4 = true ^ a ^ b ^ d Light 5 = true ^ a ^ C = true Light 6 ^ ^ b = = = = = = = = = = = repeat 1 ~ 6 = = = = = = = = = = = = = = = true Light 7 ^ a ^ ^ c d 8 = true Light ^ ^ b Light = 9 true ^ a ^ c Light 10 = true ^ a ^ b ^ dCopy the code

It can be found that the state of light bulb III = the state of light bulb II % 6i. You can also find the cycle by simply looking at the least common divisor of the four operations, and you can find all the states of the first six light bulbs.

And then it simplifies to 3

If n>3 is further considered, it can be found that the operation that determines all light bulbs is ABCD. If the states of the first three light bulbs are determined, a quaternion equation can be obtained to determine whether the operation of ABCD is performed. In other words, the states of the first three light bulbs can determine the states of all subsequent light bulbs. Proof is as follows:

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
Copy the code

The above reasons show that it is reasonable to take n=min(n,3)n =min(n,3)n =min(n,3) without losing generality.

The first three light bulbs have a total of eight states, that is, the following light bulb states are determined by eight, all light bulbs have a maximum of eight states.

Let’s use (a, B,c) to represent the state of the light. With a value of (1, 1, 1), (0, 1, 0), (1, 0, 1), (1, 0, 0) xor.

  • When m=0, all the lights are on and there is only one state (1, 1, 1). In this case, the answer is always one.
  • When m = 1, we can get status (0, 0, 0), (1, 0, 1), (0, 1, 0), (0, 1, 1). In this case, for n = 1, 2, 3, the answer is 2, 3, 4.
  • When m=2, we can check whether seven states can be obtained: all states except (0, 1, 1). In this case, n = 1, 2, 3, the answer is 2, 4, 7.
  • When m is equal to 3, we can get all 8 states. In this case, n = 1, 2, 3, the answer is 2, 4, 8.

The code then becomes easier to write:

class Solution {
public:
    int flipLights(int n, int m) {
        n = min(n, 3);
        if (m == 0) return 1;
        if (m == 1) return n == 1 ? 2 : n == 2 ? 3 : 4;
        if (m == 2) return n == 1 ? 2 : n == 2 ? 4 : 7;
        return n == 1 ? 2 : n == 2 ? 4 : 8; }};Copy the code

A few big names from Microsoft and Google have organized an interview question brushing group. You can add the administrator VX: SxxZs3998 to participate in the discussion and live broadcast