Bulb Switcher II

medium math case analysis

Problem

Press m unknown ops chosen from 4 toggle modes among n bulbs (initially on). Count distinct final states.

Inputn=3 m=1

Output4

Four distinct one-press outcomes.

input

def flip_lights(n, m):
    if m == 0: return 1
    if n == 1: return 2
    if n == 2: return 3 if m == 1 else 4
    return 4 if m == 1 else 7 if m == 2 else 8

function flipLights(n, m) {
  if (m === 0) return 1;
  if (n === 1) return 2;
  if (n === 2) return m === 1 ? 3 : 4;
  return m === 1 ? 4 : m === 2 ? 7 : 8;
}

int flipLights(int n, int m) {
    if (m == 0) return 1;
    if (n == 1) return 2;
    if (n == 2) return m == 1 ? 3 : 4;
    return m == 1 ? 4 : m == 2 ? 7 : 8;
}

int flipLights(int n, int m) {
    if (m == 0) return 1;
    if (n == 1) return 2;
    if (n == 2) return m == 1 ? 3 : 4;
    return m == 1 ? 4 : m == 2 ? 7 : 8;
}

Explanation

This looks like it needs heavy simulation, but it collapses into a tiny lookup table. After enough button presses the set of reachable states stops growing, so the answer only depends on a few small cases of n and m.

The key observation is that only the first three bulbs matter; bulb 4 onward just mirrors the pattern of bulbs 1, 2, 3. That shrinks the whole problem to a handful of distinct outcomes.

So the code is just a cascade of if checks. If m == 0 nothing was pressed, so there is exactly 1 state. If n == 1 the single bulb is either on or off, giving 2. If n == 2 the answer is 3 when m == 1 and 4 otherwise.

For n >= 3 the final line returns 4 when m == 1, 7 when m == 2, and 8 for any larger m.

Example: n = 3, m = 1. None of the early cases match, so we hit the last line with m == 1 and return 4 instantly in constant time.

Time: O(1) Space: O(1)