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:

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

Example function shape:

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

Examples

Consider:

n = 1
presses = 1

There is only one bulb.

Possible final states are:

off
on

So the answer is:

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:

n = 2
presses = 1

Possible final states are:

off off
on  off
off on

So the answer is:

3

Now consider:

n = 3
presses = 1

Possible final states are:

off off off
on  off on
off on  off
off on  on

So the answer is:

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:

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:

There are four buttons, so there are only:

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:

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

So we can reduce:

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:

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

Implementation

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:

n = min(n, 3)

Then we build one mask per button.

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

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:

initial = (1 << n) - 1

Then we enumerate every subset of the four buttons:

for subset in range(16):

The number of selected buttons is:

used = subset.bit_count()

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

if used > presses:
    continue

It is also invalid if the parity does not match:

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

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

state ^= masks[button]

Then we store the resulting state:

states.add(state)

The answer is the number of distinct states:

return len(states)

Testing

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: