#672

Medium

LeetCode Problem Workspace

Bulb Switcher II

Compute all unique bulb configurations after a fixed number of presses using math and bit manipulation efficiently.

math bit manipulation depth first search breadth first search

Problem Statement

You are given n bulbs in a room, numbered from 1 to n, all initially turned on. There are four buttons, each with a distinct toggle behavior affecting subsets of bulbs: one flips all bulbs, another flips bulbs with even numbers, one flips bulbs with odd numbers, and the last flips bulbs where the index is 3k+1. You must perform exactly presses button presses in total, choosing any button on each press.

Given two integers n and presses, return the number of distinct bulb configurations that can result after performing all presses. Each button press alters the bulb states according to its pattern, and combinations of presses can overlap, producing unique final states. The challenge is to calculate all possibilities efficiently using the math plus bit manipulation pattern rather than brute-force simulation.

Examples

Example 1

Input: n = 1, presses = 1

Output: 2

Status can be:

[off] by pressing button 1
[on] by pressing button 2

Example 2

Input: n = 2, presses = 1

Output: 3

Status can be:

[off, off] by pressing button 1
[on, off] by pressing button 2
[off, on] by pressing button 3

Example 3

Input: n = 3, presses = 1

Output: 4

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

Constraints

1 <= n <= 1000
0 <= presses <= 1000

Solution Approach

Analyze Button Effects with Bit Masks

Represent each button as a bit mask over the bulbs. Use bit manipulation to track toggles: flipping a bulb corresponds to XORing its bit. This pattern allows combining multiple button presses efficiently to identify unique final states.

Limit Consideration Based on n and presses

Notice that for n > 3, the behavior cycles and the number of unique outcomes is constrained by combinations of first three bulbs due to symmetry. For presses > 3, additional presses create overlapping patterns already represented by fewer presses. Use mathematical reasoning to reduce problem size.

Count Unique States with DFS or Set Enumeration

Iterate over all valid press sequences (limited by previous observations) using DFS or combinatorial enumeration. Store resulting configurations in a set to count unique states. This ensures accurate calculation without simulating all 2^n possibilities, relying on the math plus bit manipulation insight.

Complexity Analysis

Metric	Value
Time	O(1)
Space	O(1)

Time complexity is O(1) because the maximum number of unique configurations is constant, bounded by 8 for n>=3. Space complexity is O(1) as only a fixed number of configurations are stored and manipulated.

What Interviewers Usually Probe

Expect candidates to identify bit patterns representing bulb toggles.
Check if the solution avoids brute-force simulation for large n.
Probe understanding of how repeated presses affect unique states and symmetry.

Common Pitfalls or Variants

Common pitfalls

Ignoring symmetry when n > 3, overcounting states.
Not considering that extra presses beyond 3 do not create new configurations.
Attempting full 2^n simulation instead of using bit masks and math analysis.

Follow-up variants

Vary number of bulbs or buttons to test combinatorial reasoning.
Ask for maximum distinct states achievable with limited presses.
Change toggle rules to multiples other than 2 or 3 to examine pattern generalization.

FAQ

What is the main idea behind Bulb Switcher II?

The problem uses math and bit manipulation to count unique bulb configurations after presses without simulating every possibility.

Why are only the first three bulbs relevant for large n?

Because toggle patterns repeat every 3 bulbs, the final states for n > 3 are determined by the first three bulbs due to symmetry.

Can I simulate all 2^n bulb states for n = 1000?

No, brute-force is infeasible; the math plus bit manipulation pattern reduces the problem to a constant number of unique states.

How do extra presses affect the outcome?

Presses beyond 3 do not produce new unique states for n >= 3 since combinations of button effects start repeating.

Which algorithms patterns does this problem use?

It combines Math, Bit Manipulation, and optionally DFS/BFS for enumerating valid toggle sequences efficiently.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def flipLights(self, n: int, presses: int) -> int:
        ops = (0b111111, 0b010101, 0b101010, 0b100100)
        n = min(n, 6)
        vis = set()
        for mask in range(1 << 4):
            cnt = mask.bit_count()
            if cnt <= presses and cnt % 2 == presses % 2:
                t = 0
                for i, op in enumerate(ops):
                    if (mask >> i) & 1:
                        t ^= op
                t &= (1 << 6) - 1
                t >>= 6 - n
                vis.add(t)
        return len(vis)

Continue Practicing

#1457 pseudo palindromic paths in a binary tree #662 maximum width of binary tree #684 redundant connection