Bulb switcher ii

Math Bit Manipulation Depth-First Search Breadth-First Search

49.9% acceptance

Feb 20, 2026

195

245

There are n bulbs, all initially on. 4 buttons: 1: Flip all, 2: Flip even, 3: Flip odd, 4: Flip 3k+1. After exactly presses button presses, return distinct possible statuses.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

use std::collections::HashSet;
impl Solution {
  pub fn flip_lights(n: i32, presses: i32) -> i32 {
    let n = n.min(6) as usize;
    // Use BFS/brute force over (a1, a2, a3, a4) = counts mod 2 of each button
    let mut states: HashSet<Vec<u8>> = HashSet::new();
    // Each state is just the combination: a1, a2, a3, a4 each 0 or 1
    for a1 in 0..=1i32 {
      for a2 in 0..=1i32 {
        for a3 in 0..=1i32 {
          for a4 in 0..=1i32 {
            if (a1 + a2 + a3 + a4) % 2 != presses % 2 { continue; }
            if a1 + a2 + a3 + a4 > presses { continue; }
            let bulbs: Vec<u8> = (1..=n as i32).map(|i| {
              let mut on = 1u8;
              if a1 == 1 { on ^= 1; }
              if a2 == 1 && i % 2 == 0 { on ^= 1; }
              if a3 == 1 && i % 2 == 1 { on ^= 1; }
              if a4 == 1 && (i - 1) % 3 == 0 { on ^= 1; }
              on
            }).collect();
            states.insert(bulbs);
          }
        }
      }
    }
    states.len() as i32
  }
}