# LeetCode 672: Bulb Switcher II

## Problem Restatement

There are `n` bulbs labeled from `1` to `n`.

All bulbs are initially on.

There are four buttons:

| Button | Operation |
|---|---|
| Button 1 | Flip all bulbs |
| Button 2 | Flip bulbs with even labels |
| Button 3 | Flip bulbs with odd labels |
| Button 4 | Flip bulbs with labels `3k + 1`, such as `1, 4, 7, 10, ...` |

We must press buttons exactly `presses` times.

For each press, we may choose any of the four buttons.

Return the number of different final bulb states possible. The problem statement defines the same four operations and asks for the number of possible states after exactly `presses` button presses.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integers `n` and `presses` |
| Output | Number of possible final states |
| Initial state | All bulbs are on |
| Press rule | Exactly `presses` button presses |
| Repeated button | Allowed |

Example function shape:

```python
def flipLights(n: int, presses: int) -> int:
    ...
```

## Examples

Consider:

```python
n = 1
presses = 1
```

There is only one bulb.

Possible final states are:

```text
off
on
```

So the answer is:

```python
2
```

Button 1 flips the bulb off.

Button 2 flips even bulbs, but there are no even bulbs, so the bulb stays on.

Now consider:

```python
n = 2
presses = 1
```

Possible final states are:

```text
off off
on  off
off on
```

So the answer is:

```python
3
```

Now consider:

```python
n = 3
presses = 1
```

Possible final states are:

```text
off off off
on  off on
off on  off
off on  on
```

So the answer is:

```python
4
```

## First Thought: Simulate Every Button Sequence

A direct approach is to generate all possible sequences of button presses.

At each press, we have four choices.

So for `presses` operations, the number of sequences is roughly:

```text
4^presses
```

This is too large when `presses` can be up to `1000`.

We need to notice that many sequences produce the same final state.

## Key Insight

Pressing the same button twice cancels itself.

For example, if a bulb is flipped twice, it returns to its original state.

So for each button, only the parity matters:

| Press count for a button | Effect |
|---|---|
| Even | Same as not pressing it |
| Odd | Same as pressing it once |

There are four buttons, so there are only:

```text
2^4 = 16
```

possible parity combinations.

That means we can enumerate all button subsets instead of all button sequences.

## Why Only the First Three Bulbs Matter

The four operations repeat with period `6`, but for this problem the number of distinct states is completely determined by the first `min(n, 3)` bulbs.

For the first three bulbs, the four buttons act like this:

| Button | Bulb 1 | Bulb 2 | Bulb 3 |
|---|---|---|---|
| Flip all | flip | flip | flip |
| Flip even | no | flip | no |
| Flip odd | flip | no | flip |
| Flip `3k + 1` | flip | no | no |

These patterns are already enough to distinguish every possible state class.

So we can reduce:

```python
n = min(n, 3)
```

Then count possible states for only those bulbs.

## Valid Button Subsets

A subset of buttons has size `used`.

It is possible after exactly `presses` presses when:

1. `used <= presses`
2. `used` has the same parity as `presses`

The parity rule matters because extra presses must cancel in pairs.

For example, if a subset uses `1` button, it can also be produced with:

```text
3, 5, 7, ...
```

presses by pressing some button twice as extra canceling operations.

But it cannot be produced with exactly `2` presses.

## Algorithm

1. Replace `n` by `min(n, 3)`.
2. Represent the initial state as all `1` bits.
3. Build four bit masks for the four buttons.
4. Enumerate all `16` subsets of buttons.
5. For each subset:
   - Count how many buttons are selected.
   - Check whether it can be produced with exactly `presses` presses.
   - Apply the selected button masks using XOR.
   - Add the final state to a set.
6. Return the size of the set.

## Correctness

Pressing a button toggles some bulbs. Toggling the same bulb twice cancels, so the final effect of each button depends only on whether that button was pressed an odd or even number of times.

Therefore, every sequence of button presses is equivalent to one subset of the four buttons.

A subset with `used` buttons can be realized after exactly `presses` presses if and only if `used <= presses` and `used` has the same parity as `presses`. Extra presses can be added in canceling pairs, and no sequence can change parity without changing which buttons have odd press counts.

The algorithm enumerates every possible subset of buttons and keeps exactly the subsets that can be realized after `presses` presses.

For each valid subset, XORing the corresponding masks gives the exact final bulb state, because XOR models toggling.

Since the first `min(n, 3)` bulbs determine the possible state count, counting distinct states over these bulbs gives the correct answer.

Thus, the algorithm returns exactly the number of possible final bulb states.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(1)` | Only 16 button subsets are checked |
| Space | `O(1)` | At most 16 states are stored |

## Implementation

```python
class Solution:
    def flipLights(self, n: int, presses: int) -> int:
        n = min(n, 3)

        masks = []

        for button in range(4):
            mask = 0

            for i in range(n):
                label = i + 1

                if button == 0:
                    mask |= 1 << i
                elif button == 1 and label % 2 == 0:
                    mask |= 1 << i
                elif button == 2 and label % 2 == 1:
                    mask |= 1 << i
                elif button == 3 and label % 3 == 1:
                    mask |= 1 << i

            masks.append(mask)

        states = set()
        initial = (1 << n) - 1

        for subset in range(16):
            used = subset.bit_count()

            if used > presses:
                continue

            if (presses - used) % 2 != 0:
                continue

            state = initial

            for button in range(4):
                if subset & (1 << button):
                    state ^= masks[button]

            states.add(state)

        return len(states)
```

## Code Explanation

We only need the first three bulbs:

```python
n = min(n, 3)
```

Then we build one mask per button.

For each bulb label, we decide whether that button flips it:

```python
if button == 0:
    mask |= 1 << i
elif button == 1 and label % 2 == 0:
    mask |= 1 << i
elif button == 2 and label % 2 == 1:
    mask |= 1 << i
elif button == 3 and label % 3 == 1:
    mask |= 1 << i
```

The initial state has all bulbs on:

```python
initial = (1 << n) - 1
```

Then we enumerate every subset of the four buttons:

```python
for subset in range(16):
```

The number of selected buttons is:

```python
used = subset.bit_count()
```

A subset is invalid if it uses more odd buttons than total presses:

```python
if used > presses:
    continue
```

It is also invalid if the parity does not match:

```python
if (presses - used) % 2 != 0:
    continue
```

For a valid subset, we apply each selected button with XOR:

```python
state ^= masks[button]
```

Then we store the resulting state:

```python
states.add(state)
```

The answer is the number of distinct states:

```python
return len(states)
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.flipLights(1, 0) == 1
    assert s.flipLights(1, 1) == 2

    assert s.flipLights(2, 1) == 3
    assert s.flipLights(3, 1) == 4

    assert s.flipLights(3, 2) == 7
    assert s.flipLights(3, 3) == 8

    assert s.flipLights(1000, 0) == 1
    assert s.flipLights(1000, 1) == 4
    assert s.flipLights(1000, 2) == 7
    assert s.flipLights(1000, 3) == 8

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `n=1, presses=0` | No press leaves one state |
| `n=1, presses=1` | Single bulb has two possible states |
| `n=2, presses=1` | Standard small example |
| `n=3, presses=1` | Four direct button effects |
| `n=3, presses=2` | Valid parity subsets create seven states |
| `n=3, presses>=3` | All eight states become reachable |
| Large `n` | Confirms reduction to first three bulbs |