LeetCode 672 - Bulb Switcher II

Related:
LeetCode 319 - Bulb Switcher
LeetCode 672 - Bulb Switcher II
https://leetcode.com/problems/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]

X. DP - store all values
http://www.cnblogs.com/grandyang/p/7595595.html

这道题是之前那道Bulb Switcher的拓展，但是关灯的方式改变了。现在有四种关灯方法，全关，关偶数灯，关奇数灯，关3k+1的灯。现在给我们n盏灯，允许m步操作，问我们总共能组成多少种不同的状态。博主开始想，题目没有让列出所有的情况，而只是让返回总个数。那么博主觉得应该不能用递归的暴力破解来做，一般都是用DP来做啊。可是想了半天也没想出递推公式，只得作罢。只好去参考大神们的做法，发现这道题的结果并不会是一个超大数，最多情况只有8种。转念一想，也是，如果结果是一个超大数，一般都会对一个超大数10e7来取余，而这道题并没有，所以是一个很大的hint，只不过博主没有get到。博主应该多列几种情况的，说不定就能找出规律。下面先来看一种暴力解法，首先我们先做一个小小的优化，我们来分析四种情况：

第一种情况：1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，...

第二种情况：1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，...

第三种情况：1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，...

第四种情况：1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，...

通过观察上面的数组，我们可以发现以6个为1组，都是重复的pattern，那么实际上我们可以把重复的pattern去掉而且并不会影响结果。如果n大于6，我们则对其取余再加上6，新的n跟使用原来的n会得到同样的结果，但这样降低了我们的计算量。

下面我们先来生成n个1，这里1表示灯亮，0表示灯灭，然后我们需要一个set来记录已经存在的状态，用一个queue来辅助我们的BFS运算。我们需要循环m次，因为要操作m次，每次开始循环之前，先统计出此时queue中数字的个数len，然后进行len次循环，这就像二叉树中的层序遍历，必须上一层的结点全部遍历完了才能进入下一层，当然，在每一层开始前，我们都需要情况集合s，这样每个操作之间才不会互相干扰。然后在每层的数字循环中，我们取出队首状态，然后分别调用四种方法，突然感觉，这很像迷宫遍历问题，上下左右四个方向，周围四个状态算出来，我们将不再集合set中的状态加入queue和集合set。当m次操作遍历完成后，队列queue中状态的个数即为所求

    int flipLights(int n, int m) {
        n == (n <= 6) ? n : (n % 6 + 6);
        int start = (1 << n) - 1;
        unordered_set<int> s;
        queue<int> q{{start}};
        for (int i = 0; i < m; ++i) {
            int len = q.size();
            s.clear();
            for (int k = 0; k < len; ++k) {
                int t = q.front(); q.pop();
                vector<int> next{flipAll(t, n), flipEven(t, n), flipOdd(t, n), flip3k1(t, n)};
                for (int num : next) {
                    if (s.count(num)) continue;
                    q.push(num);
                    s.insert(num);
                }
            }
        }
        return q.size();
    }

https://leetcode.com/problems/bulb-switcher-ii/discuss/107270/Easy-to-understand-Java-BFS-solution-O(m)

    public int FlipLights(int n, int m) {
        n = n <= 6 ? n : (n % 6 + 6);
        
        int flipAll =  0b11111111111 >> (11 - n);
        int flipOdd =  0b10101010101 >> (11 - n);
        int flipEven = 0b01010101010 >> (11 - n);
        int flip3rd  = 0b10010010010 >> (11 - n);
        
        var q = new HashSet<int>();
        var q2 = new HashSet<int>();
        q.Add((1 << n) - 1);
        
        for (int round = 1; round <= m; round++)
        {            
            foreach (var state in q)
            {
                q2.Add(state ^ flipAll);
                q2.Add(state ^ flipOdd);
                q2.Add(state ^ flipEven);
                q2.Add(state ^ flip3rd);                
            }
            
            q.Clear();
            var tmp = q;
            q = q2;
            q2 = tmp;
        }
        
        return q.Count;
    }

X.
https://baihuqian.github.io/2018-07-31-bulb-switcher-ii/

As before, the first 6 lights uniquely determine the rest of the lights. This is because every operation that modifies the x-th light also modifies the (x+6)$(x+6)$-th light, so the x-th light is always equal to the (x+6)$(x+6)$-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 n=min(n,3)$n=min(n,3)$ without loss of generality. The rest is now casework.

Let’s denote the state of lights by the tuple (a,b,c)$(a,b,c)$. The transitions are to XOR by (1, 1, 1), (0, 1, 0), (1, 0, 1), or (1, 0, 0).

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

When m = 1, we could get states (0, 0, 0), (1, 0, 1), (0, 1, 0)(, or (0, 1, 1). The answer in this case is either 2, 3, 4 for n = 1, 2, 3 respectively.

When m = 2, we can manually check that we can get 7 states: all of them except for (0, 1, 1). The answer in this case is either 2, 4, 7 for n = 1, 2, 3 respectively.

When m = 3, we can get all 8 states. The answer in this case is either 2, 4, 8 for n = 1, 2, 3 respectively.

https://www.jianshu.com/p/66b885237568

对于n=0或m=0即没有灯或者不进行操作，肯定最后就只有一种状态

当n=1时，即有一盏灯时，无论你进行几次操作，最后的状态就是两种，要么亮要么灭

咱们可以对四个状态进行分析会发现：
全部反转+反转奇数=反转偶数 　　　　　 全部反转+反转偶数=反转奇数
反转奇数+反转偶数=全部反转
而最后一种操作：反转(3k+1) 即(1,4,7.....)　 对于只有1盏灯和2盏灯，最后一种操作等效于反转奇数，因为只能反转1号灯,如果有第三盏，则反转奇数可以操作，第四种不能操作
所以最后会有这么几种状态
1)原始状态(经过多次操作后返回原始状态，即全亮)
2)操作1　　　　　　3)操作2　　　　　　4)操作3　　　　５)操作4
6)操作1+操作4　　　7)操作2+操作4　　　8)操作3+操作4
因此，如果每个操作都代表不同的含义(即操作4与操作2不重合，即n>3)且操作次数m大于等于2次，那么最后就有8种状态。
下面来看特殊情况：
a) n=0或者m=0:没有灯或者不操作，最后显然只有一种状态
b) n=1,此时只要m不等于0，即只要进行操作，最终就是两种状态：亮或者灭
c) n=2，若m=1,此时操作4(3k+1)和操作2(操作奇数)是一致的，所以且不能还原全亮，所以只有三种状态，操作1，或操作2(等价操作4)，或操作3
　n=2,m>=2,此时可以还原全亮(相同操作操作两遍)，再加上操作1+操作2(等价4)+操作3，所以共有4种状态
d)其他的n,只要m=1,此时可以(设n=3)操作1(000)，操作2(010)，操作3(101)，操作4(011)
　对于最上面的分析，我们知道1+2->3,2+3->1,1+3->2,所以对于操作1,2,3无论是奇数次操作，还是偶数次操作，都可以实现，而对于操作4，因为没有其他的合成，所以必须是奇数次操作才可以实现。因此若m=2,且所有的操作不重合(即n>=3),有7种
对于剩下的情况，上面8种都可以实现

http://bookshadow.com/weblog/2017/09/03/leetcode-bulb-switcher-ii/

当灯泡数n>=3，操作次数>= 3时，灯泡状态至多可能为8种：

（偶数编号灯开关和奇数编号灯开关作用等效）

1. 全亮
2. 全亮，3k + 1
3. 奇数亮
4. 奇数亮，3k + 1
5. 偶数亮
6. 偶数亮，3k + 1
7. 全灭
8. 全灭， 3k + 1

https://blog.csdn.net/huanghanqian/article/details/77857912
我们只需要考虑当 n<=2 and m < 3 的特殊情形。因为当 n >2 and m >=3, 结果肯定是 8.
The four buttons:

Flip all the lights.
Flip lights with even numbers.
Flip lights with odd numbers.
Flip lights with (3k + 1) numbers, k = 0, 1, 2, ...
如果我们使用了 button 1 和 2, 其效果等同于使用 button 3 。
类似的..

1 + 2 --> 3, 1 + 3 --> 2, 2 + 3 --> 1
所以，只有 8 种情形。

All_on, 1, 2, 3, 4, 1+4, 2+4, 3+4

并且当 n>2 and m>=3 时，我们就能够获得所有的情形。

以下是另外一种解释的方法：

这 4 个按钮代表了 4 种数字。
x % 2 == 1 && x % 3 == 1, such as x == 1;
x % 2 == 1 && x % 3 != 1, such as x == 3;
x % 2 == 0 && x % 3 == 1, such as x == 4;
x % 2 == 0 && x % 3 != 1, such as x == 2.

因此有 8 种独立的按钮操作（假设原来的状态是 on, on, on, on） :
1                                               (off, off, off, off)
2                                               (on, off, on, off)
3                                               (off, on, off, on)
4                                               (off, on, on, off)
1 + 4                                         (on, off, off, on)
2 + 4                                         (off, off, on, on)
3 + 4                                         (on, on, off, off)
1 + 2 + 3 == 3 + 3                    (on, on, on, on)
因为 1 + 2 == 3, 2 + 3 == 1, 1 + 3 == 2, 1 + 2 + 4 == 3 + 4， 2 + 3 + 4 == 1 + 4，1 + 3 + 4 == 2 + 4， 1 + 2 + 3 + 4 == 3 + 3 + 4 == 4。

当 m == 0 时, 无事发生，只有 1 种状态。

当 n == 1 时, bulb 可以为 "on" 状态(使用按钮 2 来按动偶数开关，不会造成任何变化 )。也可以为 "off" 状态(使用了按钮 1 or 3 or 4 )。
操作 2 = 操作 1+操作 3 。操作 3 = 操作 1 + 操作 2 。操作 1 = 操作 2 + 操作 3 。因此，对于奇数次操作还是偶数次操作，我们都可以得到相同的状态。 当 n == 1 时，结果始终为 2 ，始终能得到 2 个状态。

当 n == 2 时, 有 4 种可能的状态。"on, off" == 2 ==1 + 3 。   "off, on" == 3 == 1 + 2。    "off, off" == 1 == 2 + 3。    "on, on" == 1 + 1 == 2 + 3 + 1 == 1 + 3 + 3 + 1 ==  2 + 2 == 3 + 3 == 4 + 4 。除了状态 "on, on" 需要 2 次或者 2 次以上的操作，其他状态都可以通过任意奇数/偶数操作来得到。

当 n == 3 时, 8 种 不同的状态都有可能发生。使用跟上面同样的分析方法，我们可以发现除了 m == 1 and m == 2 的情形, 其他的情形都能够得到 8 种状态。

class Solution {
    public int flipLights(int n, int m) {
        if(m==0) return 1;
        if(n==1) return 2;
        if(n==2&&m==1) return 3;
        if(n==2) return 4;
        if(m==1) return 4;
        if(m==2) return 7;
        if(m>=3) return 8;
        return 8;
    }
}
还有大神表示，这道题或许可以考虑用 bit manipulation 来做。因为这 4 个操作可以看成是：对  111, 010, 101, 100 来进行 xor 操作。
还有大神表示，这道题可以有 DP 的思路。

 dp with m rows and n columns。dp[ i ][ j ] 表示 i 个操作 j 个灯泡 能得到的最多状态数（ i 与 j 从 1 开始计数）。假设 m == 5 ， n == 7, 那么 dp 如下所示：

2, 3, 4, 4, 4, 4, 4,
2, 4, 7, 7, 7, 7, 7,
2, 4, 8, 8, 8, 8, 8,
2, 4, 8, 8, 8, 8, 8,
2, 4, 8, 8, 8, 8, 8,
https://blog.csdn.net/u012737193/article/details/79232716
我们将3k+1的值定义为内部值，非3k+1的值定义为外部值，

容易发现，当n>=4的时候，内部值和外部值都有计数和偶数，这里还有一个规律，就是对于一组n，m能够得到的灯泡状态，进行奇数次变换或者是偶数次变换之后能够变回开始的状态，因此对于n，m2，m2>=m+2包含n，m的所有状态

当n=1的时候，当m=1的时候包含全部两种状态，m=2的时候包含全部两种状态，m>2的时候包含m=1的时候的全部状态，所以返回2

当n=2的时候，当m=1的时候包含3种状态，m=2的时候包含4种状态，m=3包含全部状态，m>3的时候包含m=2的全部状态也就是全部2种状态

当n>2的时候，当m=1的时候包含7种状态，当m=2的时候包含8种状态，m=3的时候包含全部8种状态，m>3的时候包含m=2的全部状态也就是8种状态

上面那个方法虽然正确，但是有些复杂了，由于这道题最多只有8中情况，所以很适合分情况来讨论：

- 当m和n其中有任意一个数是0时，返回1

- 当n = 1时

只有两种情况，0和1

- 当n = 2时，

这时候要看m的次数，如果m = 1，那么有三种状态 00，01，10

当m > 1时，那么有四种状态，00，01，10，11

- 当m = 1时，

此时n至少为3，那么我们有四种状态，000，010，101，011

- 当m = 2时，

此时n至少为3，我们有七种状态：111，101，010，100，000，001，110

- 当m > 2时，

此时n至少为3，我们有八种状态：111，101，010，100，000，001，110，011

    int flipLights(int n, int m) {
        if (n == 0 || m == 0) return 1;
        if (n == 1) return 2;
        if (n == 2) return m == 1 ? 3 : 4;
        if (m == 1) return 4;
        return m == 2 ? 7 : 8;
    }

If you look at the operations, they are operations modulo 2 and 3. So you only need consider a sequence of 6 bulbs. Every 6 bulbs in a row share same states.
https://leetcode.com/problems/bulb-switcher-ii/discuss/107269/Java-O(1)
This code is wrong. Fails for example n=0, m=1. Correct answer is 1. You return 4. Judge expects 3. Sigh. No idea why the judge didn't include all cases for n and m up to let's say 20.

We only need to consider special cases which n<=2 and m < 3. When n >2 and m >=3, the result is 8.
The four buttons:

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

If we use button 1 and 2, it equals to use button 3.
Similarly...

1 + 2 --> 3, 1 + 3 --> 2, 2 + 3 --> 1
So, there are only 8 cases.

All_on, 1, 2, 3, 4, 1+4, 2+4, 3+4

And we can get all the cases, when n>2 and m>=3.

    public int flipLights(int n, int m) {
        if(m==0) return 1;
        if(n==1) return 2;
        if(n==2&&m==1) return 3;
        if(n==2) return 4;
        if(m==1) return 4;
        if(m==2) return 7;
        if(m>=3) return 8;
        return 8;
    }