[LeetCode] Bulb Switcher II

672. Bulb Switcher II

There is a room with n bulbs labeled from 1 to n that all are turned on initially, and four buttons on the wall. Each of the four buttons has a different functionality where:

  • Button 1: Flips the status of all the bulbs.
  • Button 2: Flips the status of all the bulbs with even labels (i.e., 2, 4, …).
  • Button 3: Flips the status of all the bulbs with odd labels (i.e., 1, 3, …).
  • Button 4: Flips the status of all the bulbs with a label j = 3k + 1 where k = 0, 1, 2, … (i.e., 1, 4, 7, 10, …).

You must make exactly presses button presses in total. For each press, you may pick any of the four buttons to press.

Given the two integers n and presses, return the number of different possible statuses after performing all presses button presses.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
int bitOp(int a, int b) {
int i = 0, res = 0;
while(a != 0 or b != 0) {
int bi = b & 1 ? !(a & 1) : (a & 1);
res += bi * (1<<i);
i++;
a>>=1; b>>=1;
}
return res;
}
public:
int flipLights(int n, int presses) {
int bits = (1<<min(n, 3)) - 1;
int odd = bits & 5, even = bits & 6, over = bits, optional = 1;
unordered_set<int> res;
res.insert(bits);
presses = min(presses, 3);
while(presses--) {
unordered_set<int> flip;
for(auto& bi : res) {
flip.insert(bitOp(bi,odd));
flip.insert(bitOp(bi,even));
flip.insert(bitOp(bi,over));
if(n >= 3) flip.insert(bitOp(bi,optional));
}

swap(res, flip);
}

return res.size();
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/02/01/PS/LeetCode/bulb-switcher-ii/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.