# 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].

``````class Solution {
public:
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();
}

int flipAll(int t, int n) {
int x = (1 << n) - 1;
return t ^ x;
}

int flipEven(int t, int n) {
for (int i = 0; i < n; i += 2) {
t ^= (1 << i);
}
return t;
}

int flipOdd(int t, int n) {
for (int i = 1; i < n; i += 2) {
t ^= (1 << i);
}
return t;
}

int flip3k1(int t, int n) {
for (int i = 0; i < n; i += 3) {
t ^= (1 << i);
}
return t;
}
};
``````

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

- 当n = 1时

- 当n = 2时，

- 当m = 1时，

- 当m = 2时，

- 当m > 2时，

``````class Solution {
public:
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;
}
};
``````

``````class Solution {
public:
int flipLights(int n, int m) {
n = min(n, 3);
return min(1 << n, 1 + m * n);
}
};
``````

Bulb Switcher

https://discuss.leetcode.com/topic/102022/c-concise-code-o-1

https://discuss.leetcode.com/topic/102395/2-short-lines-simple-formula

https://discuss.leetcode.com/topic/102227/short-and-clean-java-o-1-solution

https://discuss.leetcode.com/topic/102107/easy-to-understand-java-bfs-solution-o-m

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation