Bulb Switcher II

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.

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

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