Skip to main content
Talentd

Bulb Switcher II - Solution & Explanation

MediumMathBit ManipulationDepth-First SearchBreadth-First Search12 min readAsked at: Microsoft
Practice this problem

Problem Statement

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

Approach Overview

Problem 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.

Approach 1: Brute Force Simulation

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:

  • If there are no presses, only one configuration is possible: all lights on.
  • For n = 1: Two configurations (on, off) after one press.
  • For n = 2 and one press: Three configurations possible, else it's four for more presses.
  • For n >= 3: The number of unique states increases to a maximum of 8 due to periodicity and button effect overlap.

Code

PythonCJavaC++C#JavaScript

Python

C

Java

C++

C#

JavaScript

Complexity

Time Complexity: O(1) - Constant time due to direct evaluation based on provided conditions.
Space Complexity: O(1) - Uses fixed space.

Try this approach in the editor →

Approach 2: Analytical Pattern Recognition

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.

Code

PythonCJavaC++C#JavaScript

Python

C

Java

C++

C#

JavaScript

Complexity

Time Complexity: O(1) - Executes in constant time.
Space Complexity: O(1) - Minimal variable usage.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Simulation

Time Complexity: O(1) - Constant time due to direct evaluation based on provided conditions.
Space Complexity: O(1) - Uses fixed space.

Analytical Pattern Recognition

Time Complexity: O(1) - Executes in constant time.
Space Complexity: O(1) - Minimal variable usage.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Simulation (BFS/DFS)O(2^p * n)O(2^n)Useful for understanding switch effects and verifying patterns
Analytical Pattern RecognitionO(1)O(1)Best solution for interviews and production due to constant-time reasoning

Video Solution

Bulb Switcher II - Asked in Microsoft - Codexplained • HackerEarth • 4,329 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Bulb Switcher II easy or hard?
Bulb Switcher II is classified as a Medium difficulty problem. The implementation itself is short, but recognizing the repeating bulb patterns and reducing the state space to three bulbs requires mathematical insight.
Bulb Switcher II Python/Java solution
The Python or Java implementation for the optimal solution usually consists of a few conditional checks based on n and presses. Since the number of states is fixed, the code directly returns values such as 2, 3, 4, 7, or 8 depending on the case.
How to solve Bulb Switcher II in O(1)?
Reduce the problem to the first three bulbs since the switch patterns repeat for larger indices. Enumerate the maximum number of unique configurations achievable for different values of presses. For n ≥ 3: presses=1 gives 4 states, presses=2 gives 7 states, and presses ≥ 3 gives 8 states.
What is the best approach for Bulb Switcher II?
The optimal approach uses analytical pattern recognition. By observing that bulb states repeat after the first three positions, the problem reduces to analyzing a small fixed set of patterns. This leads to an O(1) time and O(1) space solution instead of simulating all switch presses.
Is Bulb Switcher II asked at Google/Amazon/Meta?
Bulb Switcher II represents the type of reasoning-heavy math and bit manipulation problems commonly asked in top tech interviews. Variants of switch toggling and state reduction problems appear in interviews at companies like Google, Amazon, and Meta.
What data structure is used in Bulb Switcher II?
Brute force solutions typically use a set or hash set to track unique bulb configurations while exploring states with BFS or DFS. The optimal solution mainly relies on mathematical reasoning and bit manipulation rather than complex data structures.
What is the time complexity of Bulb Switcher II?
The optimal analytical solution runs in O(1) time because the number of possible bulb states is bounded (maximum of 8). A brute force simulation using BFS or DFS can take up to O(2^p * n) time depending on how many press combinations are explored.

Ready to solve this problem?

Practice Bulb Switcher II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Bulb Switcher

Next

Number of Times Binary String Is Prefix-Aligned