Bulb Switcher II Problem

Problem

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.

Examples

Example 1:

1
2
3
4
5
6
7

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

Example 2:

1
2
3
4
5
6
7
8

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:

1
2
3
4
5
6
7
8
9

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

Solution

Method 1 – State Enumeration with Bitmasking

Intuition

The key idea is that, due to the symmetry and the limited number of bulbs affected by each button, the number of unique states is much smaller than it seems. For n > 3, the pattern repeats, so we only need to consider the first 3 bulbs. We can enumerate all possible button press combinations (since there are only 4 buttons) and count the unique resulting states.

Approach

  1. Limit n to 3, as bulbs beyond the third repeat the pattern.
  2. For each possible combination of button presses (up to 4 buttons, each can be pressed or not), check if the total number of presses matches the required parity (since order doesn’t matter).
  3. For each valid combination, simulate the effect on the bulbs and record the resulting state.
  4. Return the number of unique states.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int flipLights(int n, int presses) {
        n = std::min(n, 3);
        std::unordered_set<int> ans;
        for (int a = 0; a < 2; ++a)
        for (int b = 0; b < 2; ++b)
        for (int c = 0; c < 2; ++c)
        for (int d = 0; d < 2; ++d) {
            if (a + b + c + d > presses || (a + b + c + d) % 2 != presses % 2) continue;
            int bulbs[3] = {1, 1, 1};
            if (a) bulbs[0] ^= 1, bulbs[1] ^= 1, bulbs[2] ^= 1;
            if (b) bulbs[1] ^= 1;
            if (c) bulbs[0] ^= 1, bulbs[2] ^= 1;
            if (d) bulbs[0] ^= 1;
            int state = bulbs[0] << 2 | bulbs[1] << 1 | bulbs[2];
            ans.insert(state);
        }
        return ans.size();
    }
};
 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
34
35
36

func flipLights(n int, presses int) int {
    if n > 3 {
        n = 3
    }
    ans := map[int]struct{}{}
    for a := 0; a < 2; a++ {
        for b := 0; b < 2; b++ {
            for c := 0; c < 2; c++ {
                for d := 0; d < 2; d++ {
                    if a+b+c+d > presses || (a+b+c+d)%2 != presses%2 {
                        continue
                    }
                    bulbs := []int{1, 1, 1}
                    if a > 0 {
                        bulbs[0] ^= 1
                        bulbs[1] ^= 1
                        bulbs[2] ^= 1
                    }
                    if b > 0 {
                        bulbs[1] ^= 1
                    }
                    if c > 0 {
                        bulbs[0] ^= 1
                        bulbs[2] ^= 1
                    }
                    if d > 0 {
                        bulbs[0] ^= 1
                    }
                    state := bulbs[0]<<2 | bulbs[1]<<1 | bulbs[2]
                    ans[state] = struct{}{}
                }
            }
        }
    }
    return len(ans)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int flipLights(int n, int presses) {
        n = Math.min(n, 3);
        Set<Integer> ans = new HashSet<>();
        for (int a = 0; a < 2; a++)
        for (int b = 0; b < 2; b++)
        for (int c = 0; c < 2; c++)
        for (int d = 0; d < 2; d++) {
            if (a + b + c + d > presses || (a + b + c + d) % 2 != presses % 2) continue;
            int[] bulbs = {1, 1, 1};
            if (a == 1) { bulbs[0] ^= 1; bulbs[1] ^= 1; bulbs[2] ^= 1; }
            if (b == 1) { bulbs[1] ^= 1; }
            if (c == 1) { bulbs[0] ^= 1; bulbs[2] ^= 1; }
            if (d == 1) { bulbs[0] ^= 1; }
            int state = (bulbs[0] << 2) | (bulbs[1] << 1) | bulbs[2];
            ans.add(state);
        }
        return ans.size();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    fun flipLights(n: Int, presses: Int): Int {
        val m = minOf(n, 3)
        val ans = mutableSetOf<Int>()
        for (a in 0..1)
        for (b in 0..1)
        for (c in 0..1)
        for (d in 0..1) {
            if (a + b + c + d > presses || (a + b + c + d) % 2 != presses % 2) continue
            val bulbs = intArrayOf(1, 1, 1)
            if (a == 1) { bulbs[0] = bulbs[0] xor 1; bulbs[1] = bulbs[1] xor 1; bulbs[2] = bulbs[2] xor 1 }
            if (b == 1) bulbs[1] = bulbs[1] xor 1
            if (c == 1) { bulbs[0] = bulbs[0] xor 1; bulbs[2] = bulbs[2] xor 1 }
            if (d == 1) bulbs[0] = bulbs[0] xor 1
            val state = (bulbs[0] shl 2) or (bulbs[1] shl 1) or bulbs[2]
            ans.add(state)
        }
        return ans.size
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def flipLights(self, n: int, presses: int) -> int:
        n = min(n, 3)
        ans: set[int] = set()
        for a in range(2):
            for b in range(2):
                for c in range(2):
                    for d in range(2):
                        if a + b + c + d > presses or (a + b + c + d) % 2 != presses % 2:
                            continue
                        bulbs = [1, 1, 1]
                        if a: bulbs[0] ^= 1; bulbs[1] ^= 1; bulbs[2] ^= 1
                        if b: bulbs[1] ^= 1
                        if c: bulbs[0] ^= 1; bulbs[2] ^= 1
                        if d: bulbs[0] ^= 1
                        state = (bulbs[0] << 2) | (bulbs[1] << 1) | bulbs[2]
                        ans.add(state)
        return len(ans)
 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

use std::collections::HashSet;
impl Solution {
    pub fn flip_lights(n: i32, presses: i32) -> i32 {
        let n = n.min(3);
        let mut ans = HashSet::new();
        for a in 0..2 {
            for b in 0..2 {
                for c in 0..2 {
                    for d in 0..2 {
                        let total = a + b + c + d;
                        if total > presses || total % 2 != presses % 2 { continue; }
                        let mut bulbs = [1, 1, 1];
                        if a == 1 { bulbs[0] ^= 1; bulbs[1] ^= 1; bulbs[2] ^= 1; }
                        if b == 1 { bulbs[1] ^= 1; }
                        if c == 1 { bulbs[0] ^= 1; bulbs[2] ^= 1; }
                        if d == 1 { bulbs[0] ^= 1; }
                        let state = (bulbs[0] << 2) | (bulbs[1] << 1) | bulbs[2];
                        ans.insert(state);
                    }
                }
            }
        }
        ans.len() as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    flipLights(n: number, presses: number): number {
        n = Math.min(n, 3);
        const ans = new Set<number>();
        for (let a = 0; a < 2; a++)
        for (let b = 0; b < 2; b++)
        for (let c = 0; c < 2; c++)
        for (let d = 0; d < 2; d++) {
            if (a + b + c + d > presses || (a + b + c + d) % 2 !== presses % 2) continue;
            const bulbs = [1, 1, 1];
            if (a) { bulbs[0] ^= 1; bulbs[1] ^= 1; bulbs[2] ^= 1; }
            if (b) { bulbs[1] ^= 1; }
            if (c) { bulbs[0] ^= 1; bulbs[2] ^= 1; }
            if (d) { bulbs[0] ^= 1; }
            const state = (bulbs[0] << 2) | (bulbs[1] << 1) | bulbs[2];
            ans.add(state);
        }
        return ans.size;
    }
}

Complexity

  • ⏰ Time complexity: O(1), since the number of possible states is constant (at most 16).
  • 🧺 Space complexity: O(1), as the set of unique states is also constant in size.