Bulb Switcher II: Pattern Analysis with Four Operations

672. Bulb Switcher II gives you a room with n bulbs, all initially turned on. You have four button operations and can press buttons a total of m times (you can press the same button more than once). The question: how many distinct bulb configurations are possible after exactly m presses?

This problem looks like it could explode into a huge search space, but a few key observations collapse it down to a handful of cases you can count on your fingers.

The four operations

Each button toggles a specific set of bulbs:

1. Flip all - toggle every bulb (positions 1, 2, 3, 4, ...)
2. Flip odd - toggle bulbs at odd positions (1, 3, 5, ...)
3. Flip even - toggle bulbs at even positions (2, 4, 6, ...)
4. Flip 3k+1 - toggle bulbs at positions 1, 4, 7, 10, ... (every position of the form 3k + 1)

Notice that "flip all" equals "flip odd" plus "flip even." That is not a coincidence, and it tells you the operations are not fully independent.

Key insight: pressing twice cancels out

If you press the same button twice, you toggle the same set of bulbs twice, which brings them back to their original state. That means pressing a button an even number of times is the same as not pressing it at all, and pressing it an odd number of times is the same as pressing it once.

Order does not matter either. Toggling bulb 3 then bulb 5 gives the same result as toggling bulb 5 then bulb 3. So the only thing that matters is the parity of how many times each button was pressed.

This reduces the problem to: which subsets of (button 1, button 2, button 3, button 4) can you activate with exactly m presses? Since each button is either "pressed" (odd times) or "not pressed" (even times), there are at most 2^4 = 16 possible combinations.

But many of those 16 combinations produce the same bulb configuration. And not all 16 are reachable with every value of m.

Only the first 3 bulbs matter

Here is the second big insight. Look at how the four operations affect bulb positions:

• Position 1: toggled by operations 1, 2, and 4
• Position 2: toggled by operations 1 and 3
• Position 3: toggled by operations 1 and 2
• Position 4: toggled by operations 1, 3, and 4
• Position 5: toggled by operations 1 and 2
• Position 6: toggled by operations 1 and 3

Position 5 has the exact same toggle pattern as position 3. Position 6 matches position 2. The pattern repeats with period 6 (the LCM of 1, 2, and 3). But even within the first 6, positions 4 through 6 are determined by positions 1 through 3. So you only need to track the first 3 bulbs. Every bulb beyond that is redundant.

This means the answer cannot exceed 2^3 = 8 distinct states for the first 3 bulbs. In practice, it is exactly 8 when n >= 3 and m >= 3.

The solution

With all of that analysis, the answer is a pure case breakdown:

def flip_lights(n, presses):
    if presses == 0:
        return 1
    if n == 1:
        return 2
    if n == 2:
        return 3 if presses == 1 else 4
    if presses == 1:
        return 4
    if presses == 2:
        return 7
    return 8

Walking through each case

Let's trace through the logic:

m = 0: No presses means no changes. There is exactly 1 configuration: all bulbs on. Return 1.

n = 1: With a single bulb, any operation either toggles it or does not. You end up with the bulb on or off. Return 2.

n = 2, m = 1: With two bulbs and one press, you can press any of the 4 buttons. But "flip all" gives (off, off), "flip odd" gives (off, on), "flip even" gives (on, off), and "flip 3k+1" gives (off, on), which matches "flip odd." That is 3 distinct states. Return 3.

n = 2, m >= 2: With two or more presses, you can reach all 4 possible states for two bulbs: (on, on), (off, off), (off, on), (on, off). Return 4.

n >= 3, m = 1: Four buttons, one press. Each button produces a different state on the first 3 bulbs. Return 4.

n >= 3, m = 2: Two presses means you pick 0 or 2 buttons (since pressing 2 different buttons uses both presses, and pressing 1 button twice cancels to 0 presses, which is the same as m = 0). Actually, you can also effectively press 0 buttons by pressing the same one twice. Enumerating the combinations of 0 or 2 active buttons out of 4 gives C(4,0) + C(4,2) = 1 + 6 = 7 subsets. Each produces a distinct state on the first 3 bulbs. Return 7.

n >= 3, m >= 3: With 3 or more presses, you can activate any subset of 1, 2, 3, or 4 buttons (matching the parity of m). Combined with the even-parity subsets from m = 2, all 8 distinct states are reachable. Return 8.

Complexity

Both approaches run in constant time and constant space. The "enumerate" approach would loop through 16 combinations and check which produce unique states, but 16 is a fixed number. The case analysis approach skips the enumeration entirely by precomputing the answers.

Edge cases

• m = 0: Always returns 1 regardless of n. No presses, no changes.
• n = 1: Only one bulb exists. Any combination of operations either flips it or leaves it. Two states total.
• n = 2: The third bulb does not exist, so some operations that would differ on 3 bulbs collapse to the same effect on 2. Splits into m = 1 (3 states) and m >= 2 (4 states).
• Very large n: Does not matter. Once n >= 3, the answer depends only on m. The first 3 bulbs capture all the variation.
• Very large m: Does not matter either. Once m >= 3, all 8 states are reachable and the answer is 8 (for n >= 3).

The building blocks

Parity-based cancellation

The core observation that pressing a button twice cancels out is an instance of XOR / involution reasoning. Anytime an operation is its own inverse, you only care about parity. This shows up in problems involving light switches, XOR queries, and toggle-based puzzles. Recognizing the cancellation pattern instantly halves the search space (or more).

Reduction by symmetry

The four operations interact in structured ways. "Flip all" is "flip odd" combined with "flip even." This linear dependency over GF(2) means the effective dimension of the operation space is smaller than 4. The period-6 repetition of toggle patterns further reduces the problem to just 3 bulbs. Whenever you see overlapping operations, look for dependencies that shrink the state space.

Exhaustive small-case enumeration

With at most 2^4 = 16 button subsets and only 3 bulbs that matter, you could brute-force the entire problem by hand. Sometimes the best algorithm insight is realizing the problem is small enough to enumerate completely. The case analysis is just a clean packaging of that enumeration.

From understanding to recall

The fact to lock in: each button is on or off (parity), and only the first 3 bulbs matter (period-6 structure). From there, the case table follows by counting reachable subsets for each value of m. You do not need to memorize the exact numbers. If you remember the two key reductions, you can re-derive the cases in an interview by quickly listing the 16 subsets and checking which produce distinct 3-bulb states.

The reasoning chain is: toggle twice cancels, order irrelevant, subset parity matters, only 3 bulbs independent, enumerate small cases. That chain is the real skill this problem tests.

Related posts

• Bulb Switcher - The original bulb problem where divisor counting reveals that only perfect squares stay on
• Nim Game - Another problem that looks like it needs simulation but collapses to a simple mathematical pattern
• Power of Two - A single-check math problem where recognizing bit-level structure gives you an instant answer