LeetCode 672 - Bulb Switcher II

LeetCode Problem 672

Difficulty: 🟡 Medium
Topics: Math, Bit Manipulation, Depth-First Search, Breadth-First Search

Solution

Problem Understanding

The problem describes a room containing n light bulbs, where every bulb starts in the on state. There are four buttons available, and each button flips a specific subset of bulbs. Flipping means changing on to off or off to on.

The four buttons behave as follows:

• Button 1 flips every bulb.
• Button 2 flips bulbs with even indices.
• Button 3 flips bulbs with odd indices.
• Button 4 flips bulbs whose positions satisfy j = 3k + 1, meaning positions 1, 4, 7, 10, ....

We must perform exactly presses button presses. A button may be pressed multiple times, and the order of presses matters operationally, although many sequences eventually produce the same final bulb configuration.

The task is to determine how many distinct final bulb states are possible after exactly presses operations.

A bulb state can be represented as a binary pattern. For example:

• [on, off, on]
• [off, off, off]

Two sequences of button presses count as the same result if they produce the same final configuration.

The constraints are important:

• n can be as large as 1000
• presses can also be as large as 1000

A naive simulation over all possible sequences would be enormous because there are 4^presses possible button sequences. Even for moderate values, this becomes computationally infeasible.

The key observation is that the number of unique bulb patterns is actually very small because:

• Pressing the same button twice cancels out its effect.
• Only the parity of presses matters.
• The bulb patterns repeat periodically.
• After the first few bulbs, additional bulbs do not introduce new behavior.

Important edge cases include:

• presses = 0, where the original configuration must remain unchanged.
• n = 1, where many buttons become equivalent because they affect the same single bulb.
• Very large n, where a naive simulation would waste time processing bulbs whose behavior repeats.

Approaches

Brute Force Approach

A straightforward solution is to generate every possible sequence of button presses. Since each press has four choices, there are 4^presses sequences.

For every sequence:

1. Start with all bulbs turned on.
2. Apply each button press in order.
3. Record the resulting bulb configuration in a set.
4. Return the size of the set.

This approach is correct because it explicitly enumerates every possible sequence and therefore cannot miss any reachable configuration.

However, the complexity becomes unacceptable very quickly. For example:

• presses = 20 already produces more than one trillion sequences.

Even though many sequences collapse into the same final state, brute force still wastes time exploring all possibilities.

Key Insight for the Optimal Solution

The important mathematical observation is that pressing a button twice has no effect overall.

For example:

• Flip all bulbs once → bulbs change
• Flip all bulbs again → bulbs return to original state

Therefore, each button only matters modulo 2:

• Pressed an even number of times → no net effect
• Pressed an odd number of times → effect applied once

Since there are only four buttons, each button can be either:

• used
• unused

This creates at most:

$$2^4 = 16$$

distinct button combinations.

Another critical observation is that bulb behavior repeats after the first three bulbs. Any bulb beyond position 3 behaves identically to one of the earlier bulbs under all button operations.

Therefore:

• we only need to analyze the first min(n, 3) bulbs
• we only need to enumerate 16 button masks

This reduces the problem from exponential in presses to constant time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(4^presses × n)	O(4^presses)	Enumerates every possible press sequence
Optimal	O(1)	O(1)	Enumerates only 16 effective button combinations

Algorithm Walkthrough

1. Reduce the bulb count to at most 3.

The behavior of bulbs repeats periodically. Beyond the first three bulbs, no new independent state information appears. Therefore we compute:

effectiveBulbs = min(n, 3)

2. Enumerate all possible button combinations.

Since each button either contributes or does not contribute to the final state, we use a 4-bit mask from 0 to 15.

Each bit represents whether a button is pressed an odd number of times. 3. Count how many buttons are active in the mask.

For each mask, compute:

numberOfPressedButtons

This matters because we must perform exactly presses operations. 4. Check whether the mask is reachable.

A mask is valid only if:

• the number of active buttons does not exceed presses
• the parity matches

Why parity matters:

• extra presses can always be canceled in pairs
• therefore only odd/even parity matters

The condition becomes:

activeButtons <= presses
and
(activeButtons % 2) == (presses % 2)

5. Simulate the bulb state.

Start with all bulbs on.

For each bulb position:

• determine whether each active button flips it
• compute the final state using XOR logic

6. Store the resulting pattern.

Convert the bulb states into a tuple or string and insert into a set.

Using a set automatically removes duplicates. 7. Return the number of unique states.

The answer is simply:

len(states)

Why it works

Each button operation is its own inverse, meaning pressing it twice cancels the effect completely. Therefore only the parity of button usage matters. Since there are only four buttons, there are only 16 meaningful combinations.

Additionally, the bulb patterns repeat after the first three bulbs, so larger n values do not create additional unique behaviors. Enumerating all valid parity-compatible button combinations guarantees that every reachable final configuration is considered exactly once.

Python Solution

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

        states = set()

        for mask in range(16):
            button_count = bin(mask).count("1")

            if button_count > presses:
                continue

            if button_count % 2 != presses % 2:
                continue

            bulbs = [1] * n

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

                # Button 1
                if mask & 1:
                    bulbs[i] ^= 1

                # Button 2
                if (mask & 2) and bulb_index % 2 == 0:
                    bulbs[i] ^= 1

                # Button 3
                if (mask & 4) and bulb_index % 2 == 1:
                    bulbs[i] ^= 1

                # Button 4
                if (mask & 8) and bulb_index % 3 == 1:
                    bulbs[i] ^= 1

            states.add(tuple(bulbs))

        return len(states)

The implementation begins by reducing n to at most 3 because larger bulb indices do not introduce new behavior patterns.

A set named states stores all distinct bulb configurations.

The loop iterates through all 16 possible button masks. Each mask represents which buttons are pressed an odd number of times.

For every mask:

• button_count counts how many buttons are active.
• Masks exceeding the allowed number of presses are discarded.
• Masks with incorrect parity are also discarded.

The bulb array starts as all 1s, representing bulbs turned on.

Each button condition is checked independently:

• mask & 1 means button 1 is active.
• mask & 2 means button 2 is active.
• mask & 4 means button 3 is active.
• mask & 8 means button 4 is active.

The XOR operation (^= 1) flips the bulb state.

Finally, the bulb configuration is converted into a tuple and added to the set. The size of the set is returned as the answer.

Go Solution

package main

import (
	"math/bits"
)

func flipLights(n int, presses int) int {
	if n > 3 {
		n = 3
	}

	states := make(map[[3]int]bool)

	for mask := 0; mask < 16; mask++ {
		buttonCount := bits.OnesCount(uint(mask))

		if buttonCount > presses {
			continue
		}

		if buttonCount%2 != presses%2 {
			continue
		}

		var bulbs [3]int

		for i := 0; i < n; i++ {
			bulbs[i] = 1
		}

		for i := 0; i < n; i++ {
			bulbIndex := i + 1

			// Button 1
			if mask&1 != 0 {
				bulbs[i] ^= 1
			}

			// Button 2
			if mask&2 != 0 && bulbIndex%2 == 0 {
				bulbs[i] ^= 1
			}

			// Button 3
			if mask&4 != 0 && bulbIndex%2 == 1 {
				bulbs[i] ^= 1
			}

			// Button 4
			if mask&8 != 0 && bulbIndex%3 == 1 {
				bulbs[i] ^= 1
			}
		}

		states[bulbs] = true
	}

	return len(states)
}

The Go implementation closely mirrors the Python solution. The main difference is that Go uses a fixed-size array [3]int as the set key because arrays are hashable and comparable.

The math/bits package provides bits.OnesCount() for efficiently counting active bits in the mask.

Go does not have Python's dynamic tuple type, so the fixed array acts as the state representation.

Worked Examples

Example 1

Input:

n = 1
presses = 1

We reduce:

n = min(1, 3) = 1

Valid masks must:

• use exactly one effective button press parity
• have odd parity

Mask	Active Buttons	Final Bulb State
0001	Button 1	[0]
0010	Button 2	[1]
0100	Button 3	[0]
1000	Button 4	[0]

Unique states:

[0]
[1]

Answer:

2

Example 2

Input:

n = 2
presses = 1

Initial bulbs:

[1, 1]

Possible single-button results:

Button	Result
Button 1	[0, 0]
Button 2	[1, 0]
Button 3	[0, 1]
Button 4	[0, 1]

Unique states:

[0,0]
[1,0]
[0,1]

Answer:

3

Example 3

Input:

n = 3
presses = 1

Initial:

[1,1,1]

Single-button results:

Button	Result
Button 1	[0,0,0]
Button 2	[1,0,1]
Button 3	[0,1,0]
Button 4	[0,1,1]

Unique states count:

4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Only 16 masks and at most 3 bulbs are processed
Space	O(1)	The number of stored states is bounded by a constant

The solution is constant time because the algorithm never depends on the actual values of n or presses once the mathematical reductions are applied. At most:

• 16 masks
• 3 bulbs

are ever processed.

This makes the solution extremely efficient even for the maximum constraints.

Test Cases

sol = Solution()

assert sol.flipLights(1, 1) == 2  # single bulb, one press
assert sol.flipLights(2, 1) == 3  # two bulbs, one press
assert sol.flipLights(3, 1) == 4  # three bulbs, one press

assert sol.flipLights(1, 0) == 1  # no presses, original state
assert sol.flipLights(2, 0) == 1  # no presses with multiple bulbs

assert sol.flipLights(1, 2) == 2  # repeated operations collapse
assert sol.flipLights(2, 2) == 4  # multiple reachable states
assert sol.flipLights(3, 2) == 7  # known LeetCode case

assert sol.flipLights(3, 3) == 8  # all possible states reached
assert sol.flipLights(1000, 1000) == 8  # large constraints

assert sol.flipLights(4, 1) == 4  # behavior stabilizes after 3 bulbs
assert sol.flipLights(10, 2) == 7  # larger n behaves same as n=3

Test	Why
n=1, presses=1	Smallest nontrivial case
n=2, presses=1	Verifies overlapping button behavior
n=3, presses=1	Basic full example
presses=0	Ensures unchanged configuration
n=1, presses=2	Verifies parity cancellation
n=3, presses=2	Checks multiple-operation combinations
n=3, presses=3	Verifies maximum reachable states
n=1000, presses=1000	Stress test for large constraints
n>3 cases	Confirms periodicity optimization

Edge Cases

Zero Presses

When presses = 0, no operations may be performed. The only valid configuration is the original state where every bulb remains on.

This case can easily cause bugs if an implementation assumes at least one button combination must be applied. The parity check correctly handles this because only the empty mask is valid.

Single Bulb

When n = 1, many buttons become indistinguishable:

• Button 1 flips bulb 1
• Button 3 flips bulb 1
• Button 4 flips bulb 1
• Button 2 does nothing

A naive implementation may incorrectly count duplicate configurations multiple times. Using a set guarantees duplicates are collapsed into one unique state.

Large Values of n

The constraints allow n up to 1000. A naive simulation might waste time processing every bulb repeatedly.

The mathematical observation that only the first three bulbs matter prevents unnecessary work. The implementation explicitly reduces:

n = min(n, 3)

This ensures constant runtime regardless of input size.

Large Values of presses

The constraints also allow presses up to 1000. Brute force enumeration of all sequences would be impossible.

The parity observation solves this issue because pressing the same button twice cancels out. Therefore only the odd/even usage of each button matters, reducing the search space to just 16 combinations.