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.
- Difficulty: Medium
- Topics: Math, Breadth-First Search, Bit Manipulation
- Asked at: Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 + 1for somek >= 0(labels1, 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 <= 10000 <= presses <= 1000
Hints for Bulb Switcher II
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.
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.
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
- If
pressesis 0, only the all-on pattern exists: return 1. - Let
m = min(n, 3). - With one press the four buttons give 2, 3 or 4 patterns for
m= 1, 2, 3. - With two presses the reachable button sets are the empty set and every pair: 2, 4 or 7 patterns.
- 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 = 0means exactly one pattern even for largen.- 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