Scale Engineer

Bulb Switcher II

Med
#0626Time: 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.
Patterns
MathBit Manipulation
Algorithms
Depth-First SearchBreadth-First Search

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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);    }}

Complexity

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.

Trade-offs

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.

Solutions

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 (); } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem