LeetCode 0672. Bulb Switcher II Solution in Java, Python, C++, JavaScript, Go & Rust | Explanation + Code

Description

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.

 

Example 1:

Input: n = 1, presses = 1
Output: 2
Explanation: Status can be:
- [off] by pressing button 1
- [on] by pressing button 2

Example 2:

Input: n = 2, presses = 1
Output: 3
Explanation: Status can be:
- [off, off] by pressing button 1
- [on, off] by pressing button 2
- [off, on] by pressing button 3

Example 3:

Input: n = 3, presses = 1
Output: 4
Explanation: Status can be:
- [off, off, off] by pressing button 1
- [on, off, on] by pressing button 2
- [off, on, off] by pressing button 3
- [off, on, on] by pressing button 4

 

Constraints:

• 1 <= n <= 1000
• 0 <= presses <= 1000

Solutions

Solution 1

PythonJavaC++Go

class Solution: def flipLights(self, n: int, presses: int) -> int: ops = (0b111111, 0b010101, 0b101010, 0b100100) n = min(n, 6) vis = set() for mask in range(1 << 4): cnt = mask.bit_count() if cnt <= presses and cnt % 2 == presses % 2: t = 0 for i, op in enumerate(ops): if (mask >> i) & 1: t ^= op t &= (1 << 6) - 1 t >>= 6 - n vis.add(t) return len(vis)(code-box)

class Solution { public int flipLights(int n, int presses) { int[] ops = new int[] {0b111111, 0b010101, 0b101010, 0b100100}; Set<Integer> vis = new HashSet<>(); n = Math.min(n, 6); for (int mask = 0; mask < 1 << 4; ++mask) { int cnt = Integer.bitCount(mask); if (cnt <= presses && cnt % 2 == presses % 2) { int t = 0; for (int i = 0; i < 4; ++i) { if (((mask >> i) & 1) == 1) { t ^= ops[i]; } } t &= ((1 << 6) - 1); t >>= (6 - n); vis.add(t); } } return vis.size(); } }(code-box)

class Solution { public: int flipLights(int n, int presses) { n = min(n, 6); vector<int> ops = {0b111111, 0b010101, 0b101010, 0b100100}; unordered_set<int> vis; for (int mask = 0; mask < 1 << 4; ++mask) { int cnt = __builtin_popcount(mask); if (cnt > presses || cnt % 2 != presses % 2) continue; int t = 0; for (int i = 0; i < 4; ++i) { if (mask >> i & 1) { t ^= ops[i]; } } t &= (1 << 6) - 1; t >>= (6 - n); vis.insert(t); } return vis.size(); } };(code-box)

func flipLights(n int, presses int) int { if n > 6 { n = 6 } ops := []int{0b111111, 0b010101, 0b101010, 0b100100} vis := map[int]bool{} for mask := 0; mask < 1<<4; mask++ { cnt := bits.OnesCount(uint(mask)) if cnt <= presses && cnt%2 == presses%2 { t := 0 for i, op := range ops { if mask>>i&1 == 1 { t ^= op } } t &= 1<<6 - 1 t >>= (6 - n) vis[t] = true } } return len(vis) }(code-box)