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:
2, 4, ...).1, 3, ...).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 <= 10000 <= presses <= 1000Problem Overview: You have n bulbs initially turned on and four switches that flip bulbs in different patterns. After pressing switches exactly presses times, determine how many unique bulb configurations are possible.
Approach 1: Brute Force Simulation (State Exploration) (Time: O(2^p * n), Space: O(2^n))
This approach simulates all possible sequences of switch presses using Breadth-First Search or Depth-First Search. Represent the bulb state as a bitmask or string and apply each of the four switch operations to generate new states. Use a set to track unique configurations and avoid duplicates. Since many sequences produce the same result, the number of reachable states quickly stabilizes, but the naive search still explores many combinations. This method is useful for understanding the behavior of the switches and verifying patterns but becomes inefficient for larger search depths.
Approach 2: Analytical Pattern Recognition (Time: O(1), Space: O(1))
The key insight: the four switches create repeating patterns, and beyond the first three bulbs, the configuration becomes redundant. Any bulb beyond index 3 behaves identically to one of the first three due to overlapping flip rules. This reduces the problem to analyzing at most 3 bulbs and a limited set of operations. Using math reasoning and bit manipulation, you can enumerate the maximum number of unique states reachable based on n and presses. The result follows fixed cases: for example, when n ≥ 3, one press produces 4 states, two presses produce 7 states, and three or more presses produce all 8 possible patterns.
Recommended for interviews: Start by describing the brute-force state simulation to show you understand the switch operations and state transitions. Then explain the symmetry and pattern reduction that limits the effective bulb count to three. Interviewers expect the analytical approach because it reduces the problem to constant time and demonstrates strong reasoning about patterns and constraints.
The brute force method involves simulating all possible presses and tracking unique bulb statuses. Given the four button types, the problem can quickly become computationally expensive with high values of n and presses. However, for small values, especially considering n's repetitive behavior beyond 3, this approach is feasible.
This Python function handles different cases for presses:
Time Complexity: O(1) - Constant time due to direct evaluation based on provided conditions.
Space Complexity: O(1) - Uses fixed space.
By analyzing the problem and the stated button functionalities, we can deduce that the bulb statuses form repeatable patterns for n > 3. Consequently, the approach deduces patterns up to n = 3 directly, which encompasses every unique possible state combination for larger n due to periodic overlap.
The function deduces the count of unique configurations depending on presses limitations and n value, considerably reducing computational effort by recognizing recurring patterns from n=3 onwards.
Time Complexity: O(1) - Executes in constant time.
Space Complexity: O(1) - Minimal variable usage.
| Approach | Complexity |
|---|---|
| Brute Force Simulation | Time Complexity: O(1) - Constant time due to direct evaluation based on provided conditions. |
| Analytical Pattern Recognition | Time Complexity: O(1) - Executes in constant time. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation (BFS/DFS) | O(2^p * n) | O(2^n) | Useful for understanding switch effects and verifying patterns |
| Analytical Pattern Recognition | O(1) | O(1) | Best solution for interviews and production due to constant-time reasoning |
Bulb Switcher II - Asked in Microsoft - Codexplained • HackerEarth • 4,238 views views
Watch 8 more video solutions →Practice Bulb Switcher II with our built-in code editor and test cases.
Practice on FleetCode