# Bulb Switcher II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/bulb-switcher-ii)
Canonical: https://scaleengineer.com/dsa/problems/bulb-switcher-ii
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
---
## Problem
There is a room with `n` bulbs labeled from `1` to `n` that all are turned on initially, and **four buttons** on the wall. Each of the four buttons has a different functionality where:

* **Button 1:** Flips the status of all the bulbs.
* **Button 2:** Flips the status of all the bulbs with even labels (i.e., `2, 4, ...`).
* **Button 3:** Flips the status of all the bulbs with odd labels (i.e., `1, 3, ...`).
* **Button 4:** Flips the status of all the bulbs with a label `j = 3k + 1` where `k = 0, 1, 2, ...` (i.e., `1, 4, 7, 10, ...`).

You must make **exactly** `presses` button presses in total. For each press, you may pick **any** of the four buttons to press.

Given the two integers `n` and `presses`, return _the number of **different possible statuses** after performing all_ `presses` _button presses_.

**Example 1:**

**Input:** n = 1, presses = 1
**Output:** 2
**Explanation:** Status can be:
- [off] by pressing button 1
- [on] by pressing button 2

**Example 2:**

**Input:** n = 2, presses = 1
**Output:** 3
**Explanation:** 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
**Explanation:** 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`

# Approaches
## Brute-Force Simulation (BFS)
This approach simulates the button presses level by level using Breadth-First Search (BFS). It starts with the initial state (all bulbs on) and, for each press, explores all possible next states by applying each of the four button operations. A set is used to keep track of unique states at each level to avoid redundant computations.
**Time:** O(presses * S * n), where S is the maximum number of unique states at any level (at most 8). This simplifies to O(presses * n). Given the constraints, this could be around 1000 * 1000 = 10^6 operations, which, combined with string manipulations, is slow. · **Space:** O(S * n), where S is the maximum number of unique states at any level (at most 8). Since S is a small constant, this simplifies to O(n) to store the set of states as strings.
**Pros:** Simple to understand and implement as it directly models the problem statement.; Guaranteed to be correct if it runs within the time limits.
**Cons:** Highly inefficient for the given constraints on `n` and `presses`.; The state representation (a string of length up to 1000) is large, making string operations and storage in the hash set computationally expensive.; Likely to result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
This method directly translates the problem into a simulation. We treat each possible configuration of the `n` bulbs as a state. Starting from the initial state where all bulbs are on, we simulate the effect of `presses` button presses. Since the order of presses within a single step doesn't matter, we can think of this as a level-by-level exploration, characteristic of BFS. At each level (representing one press), we generate all possible new states from the states of the previous level. A `HashSet` is crucial to store the states at each level, as it automatically handles duplicates, ensuring we only count unique configurations.

```java
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int flipLights(int n, int presses) {
        if (presses == 0) {
            return 1;
        }

        Set<String> currentStates = new HashSet<>();
        char[] initialChars = new char[n];
        Arrays.fill(initialChars, '1');
        currentStates.add(new String(initialChars));

        for (int i = 0; i < presses; i++) {
            Set<String> nextStates = new HashSet<>();
            for (String s : currentStates) {
                nextStates.add(applyOp(s.toCharArray(), 1));
                nextStates.add(applyOp(s.toCharArray(), 2));
                nextStates.add(applyOp(s.toCharArray(), 3));
                nextStates.add(applyOp(s.toCharArray(), 4));
            }
            currentStates = nextStates;
        }

        return currentStates.size();
    }

    private String applyOp(char[] bulbs, int opType) {
        int n = bulbs.length;
        switch (opType) {
            case 1: // Flip all
                for (int i = 0; i < n; i++) {
                    bulbs[i] = (bulbs[i] == '1' ? '0' : '1');
                }
                break;
            case 2: // Flip even (labels 2, 4, ... -> indices 1, 3, ...)
                for (int i = 1; i < n; i += 2) {
                    bulbs[i] = (bulbs[i] == '1' ? '0' : '1');
                }
                break;
            case 3: // Flip odd (labels 1, 3, ... -> indices 0, 2, ...)
                for (int i = 0; i < n; i += 2) {
                    bulbs[i] = (bulbs[i] == '1' ? '0' : '1');
                }
                break;
            case 4: // Flip 3k+1 (labels 1, 4, ... -> indices 0, 3, ...)
                for (int i = 0; i < n; i += 3) {
                    bulbs[i] = (bulbs[i] == '1' ? '0' : '1');
                }
                break;
        }
        return new String(bulbs);
    }
}
```
### Algorithm
- Model the problem as a state transition graph where nodes are bulb configurations and edges represent button presses.
- The goal is to find the number of unique states reachable in exactly `presses` steps.
- Use a Breadth-First Search (BFS) approach. Start with a set containing just the initial state (all bulbs 'on').
- Iterate `presses` times. In each iteration, compute a new set of states by taking every state from the previous set and applying each of the four button operations.
- The state of `n` bulbs can be represented by a string of '0's and '1's. This allows for easy storage in a `HashSet` to track unique states.
- The algorithm proceeds as follows:
  1. Initialize a `Set<String>` called `currentStates` with the initial state (a string of `n` '1's).
  2. Loop `p` from 1 to `presses`:
     a. Create a new `Set<String>` called `nextStates`.
     b. For each `state` in `currentStates`:
        i. Apply button 1 operation to `state` and add the result to `nextStates`.
        ii. Apply button 2, 3, and 4 operations similarly and add their results to `nextStates`.
     c. Replace `currentStates` with `nextStates`.
  3. The size of the final `currentStates` set is the answer.

## Optimized Simulation with State Compression
This approach significantly improves upon the brute-force simulation by leveraging key properties of the button operations. It recognizes that the state of any bulb `i` is determined by its properties modulo 2 and 3. This creates a repeating pattern of bulb behaviors, allowing us to only simulate the states for a small, constant number of bulbs (e.g., `n=3` is sufficient) to distinguish all possible outcomes. This state compression makes the simulation extremely fast.
**Time:** O(1), because both `n` and `presses` are effectively capped at small constant values (3 and 3, respectively) for the logic, making the computations independent of the input size. · **Space:** O(1), as the `HashSet` and other variables used are of a small, constant maximum size.
**Pros:** Very efficient, effectively constant time, as it reduces the problem size.; Handles large `n` without any performance penalty.
**Cons:** Requires non-trivial insights into the problem's structure (periodicity and state distinguishability).; The implementation can be slightly more complex than the final mathematical approach, as it still involves some simulation logic.
### Explanation
The key observation is that the bulb states exhibit a periodic pattern. A bulb's state is affected by operations that depend on its index being even/odd (period 2) or of the form `3k+1` (related to period 3). The combined behavior repeats every `lcm(2,3)=6` bulbs. A deeper look reveals that the first 3 bulbs are enough to distinguish all 8 unique transformations that can arise from combinations of button presses. For example, `(op1, op2, op3, op4)` result in four distinct states for `n=3`: `(0,0,0)`, `(1,0,1)`, `(0,1,0)`, and `(0,1,1)`. By capping `n` at `min(n, 3)`, we can use bitmasks for an efficient simulation.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int flipLights(int n, int presses) {
        if (presses == 0) {
            return 1;
        }
        // The state of the first 3 bulbs is sufficient to distinguish all 8 transformations.
        n = Math.min(n, 3);

        Set<Integer> finalStates = new HashSet<>();
        int initialMask = (1 << n) - 1; // All bulbs on

        // Generate masks for the 4 operations for the current n
        int[] opMasks = new int[4];
        opMasks[0] = (1 << n) - 1; // Button 1: all
        for (int i = 1; i < n; i += 2) opMasks[1] |= (1 << i); // Button 2: even
        for (int i = 0; i < n; i += 2) opMasks[2] |= (1 << i); // Button 3: odd
        for (int i = 0; i < n; i += 3) opMasks[3] |= (1 << i); // Button 4: 3k+1

        if (presses == 1) {
            for (int mask : opMasks) {
                finalStates.add(initialMask ^ mask);
            }
        } else if (presses == 2) {
            // Achievable with k=0 or k=2 presses
            finalStates.add(initialMask); // k=0
            for (int i = 0; i < 4; i++) {
                for (int j = i + 1; j < 4; j++) {
                    finalStates.add(initialMask ^ opMasks[i] ^ opMasks[j]);
                }
            }
        } else { // presses >= 3
            // All 8 transformations are achievable
            for (int i = 0; i < 16; i++) {
                int finalMask = initialMask;
                if ((i & 1) > 0) finalMask ^= opMasks[0];
                if ((i & 2) > 0) finalMask ^= opMasks[1];
                if ((i & 4) > 0) finalMask ^= opMasks[2];
                if ((i & 8) > 0) finalMask ^= opMasks[3];
                finalStates.add(finalMask);
            }
        }
        return finalStates.size();
    }
}
```
*Note: The code above for `presses=2` and `presses>=3` is a simplified way to generate the reachable states, which correctly captures the number of unique outcomes for the reduced `n`.*
### Algorithm
- Observe that the four button operations affect bulbs based on their labels: all, even, odd, and `3k+1`.
- The effect of an operation on bulb `i` depends on `i mod 2` and `i mod 3`. The combined properties repeat with a period of `lcm(2, 3) = 6`.
- This periodicity implies that the state of the entire sequence of bulbs is determined by the state of the first few bulbs. Analysis shows that the first 3 bulbs are sufficient to uniquely distinguish all 8 possible transformations.
- Therefore, we can cap `n` at `min(n, 3)`. This drastically reduces the state space.
- With a small `n`, we can represent the state of the bulbs as a single integer bitmask, making operations very fast.
- The algorithm is:
  1. Handle the base case `presses == 0`, returning 1.
  2. Reduce `n` to `min(n, 3)`.
  3. Determine the set of achievable transformations based on `presses`.
     - `presses = 1`: 4 specific transformations are possible.
     - `presses = 2`: 7 specific transformations are possible.
     - `presses >= 3`: All 8 possible transformations are achievable.
  4. Pre-compute the bitmasks for the 4 basic operations for the reduced `n`.
  5. Generate the final states by applying the achievable transformations to the initial state mask.
  6. Store the results in a `HashSet` and return its size.

## Mathematical Case Analysis
This is the most optimal approach, bypassing simulation entirely. It involves a deep mathematical and combinatorial analysis to find a direct, closed-form solution. By analyzing the algebraic relationships between the button operations, the constraints on the number of presses, and how the number of bulbs `n` affects the distinguishability of the final states, we can determine the exact number of outcomes with simple conditional logic.
**Time:** O(1), as the solution consists of a few conditional checks on the input values. · **Space:** O(1), as no extra space is used that depends on the input size.
**Pros:** Extremely efficient, providing a solution in constant time and space.; The code is very simple, concise, and easy to read once the logic is understood.
**Cons:** The logic is non-obvious and requires a deep mathematical analysis of the problem's structure.; It can be very difficult to derive this solution from scratch under time pressure, such as in a coding interview.
### Explanation
The problem can be solved by analyzing the constraints and properties of the system. We can determine the number of unique states by considering the values of `n` and `presses` in a few distinct cases.

- **Case `presses = 0`**: No buttons are pressed. The bulbs remain in their initial 'on' state. There is only **1** possible status.

- **Case `n = 1`**: There is only one bulb. Button 2 (even labels) has no effect. Buttons 1, 3, and 4 all flip the first bulb. With one or more presses, we can either leave the bulb on (e.g., press button 2) or turn it off (e.g., press button 1). Thus, there are **2** possible statuses if `presses > 0`.

- **Case `n = 2`**: There are two bulbs. 
  - If `presses = 1`, we can achieve 3 states: `[off, off]` (B1), `[on, off]` (B2), `[off, on]` (B3 or B4). Total **3** statuses.
  - If `presses >= 2`, we can achieve all 4 possible states for two bulbs: `[on, on]`, `[on, off]`, `[off, on]`, `[off, off]`. Total **4** statuses.

- **Case `n >= 3`**: All 8 fundamental transformations produce unique states on the first 3 bulbs.
  - If `presses = 1`, we can use any of the 4 buttons, resulting in **4** unique statuses.
  - If `presses = 2`, analysis shows that 7 of the 8 transformations are achievable, resulting in **7** unique statuses.
  - If `presses >= 3`, all 8 transformations are achievable, resulting in **8** unique statuses.

This case analysis covers all possibilities and can be implemented with a simple set of `if-else` statements.

```java
class Solution {
    public int flipLights(int n, int presses) {
        // No presses, all bulbs remain on.
        if (presses == 0) {
            return 1;
        }

        // Case for n = 1 bulb
        if (n == 1) {
            return 2; // Can be on or off.
        }

        // Case for n = 2 bulbs
        if (n == 2) {
            if (presses == 1) {
                return 3;
            } else { // presses >= 2
                return 4;
            }
        }

        // Case for n >= 3 bulbs
        if (presses == 1) {
            return 4;
        } else if (presses == 2) {
            return 7;
        } else { // presses >= 3
            return 8;
        }
    }
}
```
### Algorithm
- The solution is derived from a complete mathematical analysis of the problem's state space.
- **Insight 1: Operation Equivalence.** Pressing a button twice cancels itself out. The order of presses does not matter. This means we only care about the parity (odd/even) of presses for each button.
- **Insight 2: Operation Dependency.** Button 1's effect is the same as pressing Button 2 and Button 3. This dependency (`op1 = op2 XOR op3`) reduces the number of independent operations, leading to at most 8 unique final transformations.
- **Insight 3: Achievability.** The set of transformations achievable with exactly `presses` presses depends on the parity of `presses`. A transformation corresponding to a combination of `k` odd-parity button presses is possible only if `k <= presses` and `k % 2 == presses % 2`.
- **Insight 4: Distinguishability.** The number of unique final *states* depends on `n`. For `n=1` and `n=2`, some of the 8 transformations produce identical results. For `n>=3`, all 8 transformations result in unique states.
- By combining these insights, we can determine the exact number of outcomes for each combination of `n` and `presses` and implement the solution using a simple set of conditional checks.

# Solutions
### Java

```java
class Solution { public int flipLights ( int n , int presses ) { int [] ops = new int [] { 0b111111 , 0b010101 , 0b101010 , 0b100100 }; Set < Integer > vis = new HashSet <>(); n = Math . min ( n , 6 ); for ( int mask = 0 ; mask < 1 << 4 ; ++ mask ) { int cnt = Integer . bitCount ( mask ); if ( cnt <= presses && cnt % 2 == presses % 2 ) { int t = 0 ; for ( int i = 0 ; i < 4 ; ++ i ) { if ((( mask >> i ) & 1 ) == 1 ) { t ^= ops [ i ]; } } t &= (( 1 << 6 ) - 1 ); t >>= ( 6 - n ); vis . add ( t ); } } return vis . size (); } }
```

### CPP

```cpp
class Solution { public: int flipLights ( int n , int presses ) { n = min ( n , 6 ); vector < int > ops = { 0b111111 , 0b010101 , 0b101010 , 0b100100 }; unordered_set < int > vis ; for ( int mask = 0 ; mask < 1 << 4 ; ++ mask ) { int cnt = __builtin_popcount ( mask ); if ( cnt > presses || cnt % 2 != presses % 2 ) continue ; int t = 0 ; for ( int i = 0 ; i < 4 ; ++ i ) { if ( mask >> i & 1 ) { t ^= ops [ i ]; } } t &= ( 1 << 6 ) - 1 ; t >>= ( 6 - n ); vis . insert ( t ); } return vis . size (); } };
```

### Python

```python
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 )
```