Bulb Switcher II

Medium
1274.

Bulb Switcher II

Bulb Switcher II is a medium coding problem on math, breadth-first search and bit manipulation, asked in Google and Microsoft interviews.

A row of n bulbs is labelled 1 to n, and every bulb starts on. A panel has four buttons:

  • Button 1 flips every bulb.
  • Button 2 flips the bulbs with even labels.
  • Button 3 flips the bulbs with odd labels.
  • Button 4 flips the bulbs whose label is 3k + 1 for some k >= 0 (labels 1, 4, 7, 10, …).

You must make exactly presses button presses in total; each press may use any of the four buttons, and a button may be pressed any number of times.

Return how many different on/off patterns of the row are possible after all the presses.

Example 1

Input
n = 1, presses = 1
Output
2
Explanation
The single bulb ends either off (buttons 1, 3 or 4) or on (button 2).

Example 2

Input
n = 2, presses = 1
Output
3
Explanation
The patterns are [off, off], [on, off] and [off, on].

Example 3

Input
n = 3, presses = 1
Output
4

Constraints

  • 1 <= n <= 1000
  • 0 <= presses <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number} presses
 * @return {number}
 */
var flipLights = function(n, presses) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Bulb Switcher II — Solution in Python, Java & C++

Bulb Switcher II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Bulb Switcher II is a medium coding problem on math, breadth-first search and bit manipulation, asked in Google and Microsoft interviews.

Problem statement

A row of n bulbs is labelled 1 to n, and every bulb starts on. A panel has four buttons:

  • Button 1 flips every bulb.
  • Button 2 flips the bulbs with even labels.
  • Button 3 flips the bulbs with odd labels.
  • Button 4 flips the bulbs whose label is 3k + 1 for some k >= 0 (labels 1, 4, 7, 10, …).

You must make exactly presses button presses in total; each press may use any of the four buttons, and a button may be pressed any number of times.

Return how many different on/off patterns of the row are possible after all the presses.

Example 1

Input: n = 1, presses = 1
Output: 2
Explanation: The single bulb ends either off (buttons 1, 3 or 4) or on (button 2).

Example 2

Input: n = 2, presses = 1
Output: 3
Explanation: The patterns are [off, off], [on, off] and [off, on].

Example 3

Input: n = 3, presses = 1
Output: 4

Constraints

  • 1 <= n <= 1000
  • 0 <= presses <= 1000

Hints for Bulb Switcher II

  1. Hint 1

    Pressing the same button twice changes nothing, so only whether each button was pressed an odd or even number of times matters — at most 16 combinations.

  2. Hint 2

    Look at which bulbs each button touches: the pattern repeats every 6 bulbs, and bulbs 4, 5 and 6 are determined by bulbs 1, 2 and 3.

  3. Hint 3

    So the answer only depends on min(n, 3) and on whether presses is 0, 1, 2 or at least 3. Work those twelve cases out by hand.

How to solve Bulb Switcher II

Only the parity of each button matters, and every bulb's state is a function of the first three bulbs' states, so the answer depends on just min(n, 3) and on presses capped at 3.

Approach

  1. If presses is 0, only the all-on pattern exists: return 1.
  2. Let m = min(n, 3).
  3. With one press the four buttons give 2, 3 or 4 patterns for m = 1, 2, 3.
  4. With two presses the reachable button sets are the empty set and every pair: 2, 4 or 7 patterns.
  5. With three or more presses every parity combination of the right size is reachable and all 8 patterns of three bulbs appear (2 and 4 for one and two bulbs).

Why it works

Toggles commute, so the outcome is decided by which buttons were used an odd number of times; a set of c buttons is reachable when c <= presses and presses - c is even (spare presses cancel in pairs). Whether a button touches bulb i depends only on i mod 2 and i mod 3, so the row repeats every 6 bulbs. Within those six, bulb 5 always equals bulb 3, bulb 6 equals bulb 2, and bulb 4 is the xor of bulbs 1, 2 and 3 — so the first three bulbs decide the whole row. Listing the toggles on bulbs 1–3 for one press gives 4 patterns; for two presses (no button, or any pair) gives 7, the missing one being button 4 alone (only bulb 1 off); with three or more presses all 8 appear. With one bulb any positive number of presses gives 2 patterns; with two bulbs one press gives 3 and two or more give 4.

Complexity

  • Time — O(1)
  • Space — O(1)

Pitfalls

  • presses = 0 means exactly one pattern even for large n.
  • Two presses give 7, not 8: the pattern reached by button 4 alone is not reachable with exactly two presses.
  • Simulating presses one at a time explodes as 4^presses — reduce to parities first.

Reference solution

Python

def flipLights(n: int, presses: int) -> int:
    m = min(n, 3)
    if presses == 0:
        return 1
    if presses == 1:
        return [2, 3, 4][m - 1]
    if presses == 2:
        return [2, 4, 7][m - 1]
    return [2, 4, 8][m - 1]

Java

public static int flipLights(int n, int presses) {
    int m = Math.min(n, 3);
    int[] one = {2, 3, 4};
    int[] two = {2, 4, 7};
    int[] many = {2, 4, 8};
    if (presses == 0) return 1;
    if (presses == 1) return one[m - 1];
    if (presses == 2) return two[m - 1];
    return many[m - 1];
}

C++

int flipLights(int n, int presses) {
    int m = min(n, 3);
    static const int one[3] = {2, 3, 4};
    static const int two[3] = {2, 4, 7};
    static const int many[3] = {2, 4, 8};
    if (presses == 0) return 1;
    if (presses == 1) return one[m - 1];
    if (presses == 2) return two[m - 1];
    return many[m - 1];
}

JavaScript

var flipLights = function(n, presses) {
    var m = Math.min(n, 3);
    if (presses === 0) return 1;
    if (presses === 1) return [2, 3, 4][m - 1];
    if (presses === 2) return [2, 4, 7][m - 1];
    return [2, 4, 8][m - 1];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Breadth-First Search (BFS) · Bit Manipulation