672. Bulb Switcher II
Problem Description
There is a room equipped with n
light bulbs, each with a distinct label ranging from 1
to n
. Initially, all bulbs are in the 'on' state. Within this room, there is a wall-mounted control panel that includes four distinct buttons, each with a unique function that affects the state of one or more bulbs:
- Button 1: Toggles the state (on/off) of all the bulbs.
- Button 2: Toggles the state of all bulbs with an even-numbered label.
- Button 3: Toggles the state of all bulbs with an odd-numbered label.
- Button 4: Toggles the state of bulbs labeled with numbers of the form
j=3k+1
(fork=0, 1, 2, ...
), which includes1, 4, 7, 10, ...
.
The task is to make exactly presses
number of button presses, and you can choose to press any button at each step. The question requires us to calculate the total number of distinct lighting configurations that can be achieved after making exactly presses
number of button presses.
For example, with n
bulbs and presses
allowed presses, what are the different ways the bulbs can be lit or unlit?
Flowchart Walkthrough
First, let's analyze Leetcode 672. Bulb Switcher II using the Flowchart. Here’s a step-by-step walkthrough:
Is it a graph?
- No: The problem of Bulb Switcher II deals with the switching on/off of bulbs based on certain operations, which does not structurally represent a graph where nodes connect via edges.
Since the problem is not a graph-based problem, the flowchart does not directly guide us to an algorithm within the scope of graph theory such as Depth-First Search (DFS). Instead, the complexity and constraints of this problem might lead us to consider combinatorial techniques outside the purview of the provided flowchart.
To use Depth-First Search (DFS) or backtracking, we need to consider each possibility of operations and their effects on the initial state of bulbs, exploring each configuration path thoroughly until all combinations of operations have been considered. This approach is relevant because:
- The operations have combinatorial effects on the bulbs.
- We strategically explore different combinations (states) of bulbs being on or off.
- DFS/backtracking helps in exploring all potential states that can result from a series of operations.
Though the flowchart does not directly lead to this conclusion due to the non-graph nature of the problem, the considerations above illustrate why DFS could be appropriate for this problem.
Intuition
To solve this problem, we notice that toggling the lights in certain patterns can lead to the same outcome. This realization can significantly reduce the number of possible configurations we need to check.
Here's the intuitive approach to find the solution:
-
Optimization of
n
: Since each press of a button flips the status of the bulbs in a certain pattern, and the patterns repeat every 6 bulbs, we can reduce anyn
greater than 6 ton % 6
, which simplifies the problem. -
Unique States Analysis: We note that after a certain number of presses, the patterns begin to repeat, and thus the number of unique states is finite. By analyzing the effects of each button press, we can establish that there aren't many different states the bulbs can be in after
presses
button presses. This is due to the symmetries and overlaps in the patterns created by each button. -
Bitmask Technique: Implementing the idea of using a bitmask to represent the state of the light bulbs and the actions of the buttons, where
1
represents a bulb turned on and0
a bulb turned off, we use bitwise operations to simulate the pressing of buttons and record the resulting state of the bulbs. -
Iterating Over Possibilities: By iterating over all possible combinations of button presses (which can be up to
2^4
because there are four buttons), we can check which combinations of button presses will result in a unique final state of the bulbs. At each iteration, we apply the respective toggles based on the pressed buttons and store the outcome in a set to avoid duplicates. -
Parity Check: We can further trim down the possibilities by recognizing that the number of presses must have the same parity (even or odd) as the number of operations to reach a specific state. This comes from the insight that toggling an even number of times will lead to the original state, while an odd number will result in a change.
-
Counting Unique States: After generating all possible states, the size of the set will be the number of unique states since a set does not contain duplicates.
Implementing these insights into code, we simulate the button presses, record the possible states, and return the count of distinct states.
Learn more about Depth-First Search, Breadth-First Search and Math patterns.
Solution Approach
The implementation of the solution involves a clever use of bit manipulation and set data structures to efficiently determine the unique states of the light bulbs after a certain number of presses.
The overall approach can be outlined as follows:
-
Minimizing
n
: The first line of action in our approach is to minimize the value ofn
(the number of bulbs) to 6 or below, as the patterns repeat every 6 bulbs. This is achieved withn = min(n, 6)
. Beyond 6 bulbs, the states just repeat and do not introduce any new combinations. -
Defining Operations: An array (or tuple)
ops
is defined, representing the outcome of each button press as a bit mask. This is a compact way to encode which bulbs are affected by each button:- Button 1 toggles all bulbs, hence
0b111111
. - Button 2 toggles bulbs at even positions, hence
0b010101
. - Button 3 toggles bulbs with odd labels, hence
0b101010
. - Button 4 toggles bulbs with labels
1, 4, 7, ...
, hence0b100100
.
- Button 1 toggles all bulbs, hence
-
Iterating Through Button Combinations: We iterate through all possible combinations of button presses using a loop
for mask in range(1 << 4)
which generates numbers from0
to15
(in binary:0000
to1111
), each representing a unique combination of button presses. -
Parity and Presses Check: For each combination, we count the number of bits (i.e., button presses) using
cnt = mask.bit_count()
and check whether the count of presses is less than or equal to the allowed number of presses and has the same parity. This eliminates unnecessary checks and focuses our attention on valid scenarios. -
Applying Toggles: If the combination is valid, we apply the toggles associated with each bit in the mask. The loop
for i, op in enumerate(ops)
goes through the operations, and if biti
in the mask is set (i.e., the corresponding button is pressed), we use an XOR operationt ^= op
to toggle the state of the bulbs affected by that button. -
Recording the State: To ensure that we're only considering the bulbs we have (
n
may be less than 6), we perform a bit maskt &= (1 << 6) - 1
of the first six positions and then shift the result to fit our number of bulbs usingt >>= 6 - n
. This final value represents the state of the light bulbs after applying the combination of button presses. -
Avoiding Duplicate States: We use a set
vis
to store unique states, preventing duplicate counts. We add the resulting statet
to this setvis.add(t)
. -
Getting the Count: After iterating through all combinations and recording the valid states, the length of the set
len(vis)
gives us the number of unique possible statuses of the bulbs, which is the solution to the problem.
By using bit masks and sets, the code efficiently simulates all possible scenarios of button presses, while avoiding redundancies and accounting for the symmetry in the buttons' operation to tally the unique final states of the light bulbs.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach using the above method with n = 3
bulbs and presses = 1
allowed press. In this scenario, we are only interested in the toggles that can happen in one press or less, so we will examine what each button does when pressed alone.
The initial state of the bulbs is all "on", which in bit representation (1 for 'on' and 0 for 'off'), starting from the rightmost bit (bulb number 1) to left, is 111
.
-
Minimizing
n
: Sincen
is already less than or equal to 6, we do not need to modifyn
. -
Defining Operations: We define the bitmasks for the given operations, considering only the first 3 bits for our
n = 3
bulbs:- Button 1 toggles all bulbs, bitmask:
111
(flips all bits). - Button 2 toggles even bulbs, bitmask:
010
(flips the middle bit). - Button 3 toggles odd bulbs, bitmask:
101
(flips the first and last bits). - Button 4 toggles bulbs with labels
1
,4
,7
, ..., but since we only have 3 bulbs, it's equivalent to toggling bulb1
, bitmask:001
(flips the last bit).
- Button 1 toggles all bulbs, bitmask:
-
Iterating Through Button Combinations: We iterate through the combinations of pressing only one button, as we are allowed only one press. We have
0000
through1000
(in binary), but since the first bit will always be0
, we care only about0001
,0010
,0100
, and1000
representing button presses 1 through 4 respectively. -
Parity and Presses Check: Since we are allowed only 1 press, we only consider combinations where the button bit count is
1
or0
. Thus, all combinations are valid because either no button is pressed or exactly one is pressed. -
Applying Toggles:
- For combination
0001
(Button 1): Initial111
toggled becomes000
(all off). - For combination
0010
(Button 2): Initial111
toggled becomes101
(middle bulb off). - For combination
0100
(Button 3): Initial111
toggled becomes010
(only the middle bulb on). - For combination
1000
(Button 4): Initial111
toggled becomes110
(last bulb off).
- For combination
-
Recording the State: Since
n=3
, no further bit masking or shifting is needed. We record these states as they are. -
Avoiding Duplicate States: We add each state to a set:
- After Button 1: Add
000
. - After Button 2: Add
101
. - After Button 3: Add
010
. - After Button 4: Add
110
.
- After Button 1: Add
-
Getting the Count: We count the number of unique statuses in our set:
{000, 101, 010, 110}
. There are 4 unique states possible withn = 3
bulbs and 1 allowed press.
Thus, the answer for n = 3
bulbs and presses = 1
press is 4
unique lighting configurations.
Solution Implementation
1class Solution:
2 def flipLights(self, n: int, presses: int) -> int:
3 # Define the operations bitmask for the 4 different types of buttons
4 operations = (0b111111, 0b010101, 0b101010, 0b100100)
5 # Since the light pattern repeats every 6 lights, limit n to 6
6 n = min(n, 6)
7
8 # Use set to avoid duplicate configurations
9 visited = set()
10
11 # Iterate over all combinations of button presses (by checking all bitmasks up to the 4th bit)
12 for mask in range(1 << 4):
13 count = bin(mask).count('1') # calculate the number of pressed buttons
14
15 # Only consider valid sequences of presses: those that match the number of presses and parity
16 if count <= presses and count % 2 == presses % 2:
17 temp = 0 # This will store the combination of flips
18 for i, operation in enumerate(operations):
19 # Apply the operation if the corresponding button was pressed
20 if (mask >> i) & 1:
21 temp ^= operation
22 # Trim the pattern to the least significant 'n' bits
23 temp &= (1 << 6) - 1
24 temp >>= 6 - n
25 visited.add(temp) # Add this pattern to the visited configurations
26
27 return len(visited) # The number of unique configurations is the size of the set
28
1class Solution {
2
3 // Method to determine the number of different light configurations possible after pressing switches
4 public int flipLights(int n, int presses) {
5
6 // Light switch operations, represented in a 6-bit pattern (max number of lights we are considering)
7 // 0b111111 -> Flip all lights
8 // 0b010101 -> Flip lights with odd indices
9 // 0b101010 -> Flip lights with even indices
10 // 0b100100 -> Flip lights at 3k+1 positions (1, 4, ...)
11 int[] operations = new int[] {0b111111, 0b010101, 0b101010, 0b100100};
12
13 // A set to record distinct light patterns after performing operations
14 Set<Integer> visitedPatterns = new HashSet<>();
15
16 // Since the pattern repeats every 6 lights, we only consider the first 6 lights
17 n = Math.min(n, 6);
18
19 // Iterate over all 16 possible combinations of the 4 operations using a bitmask
20 for (int mask = 0; mask < 1 << 4; ++mask) {
21
22 // Count the number of operations to be performed (number of set bits in mask)
23 int count = Integer.bitCount(mask);
24
25 // If this count of operations can be performed within given presses, and the parity (even/odd) matches
26 if (count <= presses && count % 2 == presses % 2) {
27
28 // Initialize the temporary light pattern to zero
29 int tempPattern = 0;
30
31 // For each operation, check if it is included in the current combination, and if so, apply XOR
32 for (int i = 0; i < 4; ++i) {
33 if (((mask >> i) & 1) == 1) {
34 tempPattern ^= operations[i];
35 }
36 }
37
38 // Mask off irrelevant bits (we only consider the first 6 lights)
39 tempPattern &= ((1 << 6) - 1);
40
41 // Shift the bits for patterns with lights less than 6, if necessary
42 tempPattern >>= (6 - n);
43
44 // Add the resulting pattern to the set of visited patterns
45 visitedPatterns.add(tempPattern);
46 }
47 }
48
49 // Return the number of distinct patterns recorded in the set
50 return visitedPatterns.size();
51 }
52}
53
1class Solution {
2public:
3 // The flipLights function determines the number of different lighting configurations
4 // that can be achieved by operating the switches a given number of times.
5 // We limit the lights and operations to minimize calculations due to symmetries.
6 int flipLights(int n, int presses) {
7 // Limit the number of lights to 6 because the pattern repeats every 6 lights.
8 n = min(n, 6);
9
10 // Define the operations corresponding to flipping lights:
11 // 1. Flip all the lights (0b111111)
12 // 2. Flip lights at even positions (0b010101)
13 // 3. Flip lights at odd positions (0b101010)
14 // 4. Flip lights at positions 1, 4, ... (0b100100)
15 vector<int> operations = {0b111111, 0b010101, 0b101010, 0b100100};
16
17 // Use a set to keep track of unique configurations after certain presses.
18 unordered_set<int> visitedConfigurations;
19
20 // Iterate over all possible combinations of operations.
21 // (1 << 4) creates a bitmask with 4 bits, iterating over all combinations of 4 switches.
22 for (int mask = 0; mask < 1 << 4; ++mask) {
23 // Count the number of bits set in the mask.
24 int count = __builtin_popcount(mask);
25
26 // Skip combinations where the number of operations doesn't match the presses.
27 // The count of operations must be the same as the number of presses modulo 2.
28 if (count > presses || count % 2 != presses % 2) continue;
29
30 // Initialize the configuration for this combination of operations.
31 int configuration = 0;
32 for (int i = 0; i < 4; ++i) {
33 // If the i-th operation is to be applied, XOR it with the current configuration.
34 if (mask >> i & 1) {
35 configuration ^= operations[i];
36 }
37 }
38
39 // Apply a mask to isolate only the bits corresponding to 'n' lights.
40 configuration &= (1 << 6) - 1;
41 // Right-shift the bits to get the correct configuration based on the number of lights.
42 configuration >>= (6 - n);
43
44 // Insert the final configuration into the set.
45 visitedConfigurations.insert(configuration);
46 }
47
48 // The number of unique configurations is the size of the set.
49 return visitedConfigurations.size();
50 }
51};
52
1// Limit the number of lights as the pattern repeats every 6 lights.
2function minLights(n: number): number {
3 return Math.min(n, 6);
4}
5
6// Define the operations corresponding to flipping lights
7const operations: number[] = [0b111111, 0b010101, 0b101010, 0b100100];
8
9// A set to keep track of unique configurations.
10const visitedConfigurations: Set<number> = new Set();
11
12// Flip all the lights based on the number of presses and return different configurations.
13function flipLights(n: number, presses: number): number {
14 n = minLights(n);
15
16 for (let mask = 0; mask < 1 << 4; ++mask) {
17 let count: number = countSetBits(mask);
18
19 // Skip combinations where the number of operations doesn't match the presses
20 if (count > presses || count % 2 !== presses % 2) continue;
21
22 let configuration: number = 0;
23 for (let i = 0; i < 4; ++i) {
24 if ((mask >> i) & 1) {
25 configuration ^= operations[i];
26 }
27 }
28
29 // Apply a mask to isolate only the bits corresponding to 'n' lights
30 configuration &= (1 << n) - 1;
31
32 visitedConfigurations.add(configuration);
33 }
34
35 // The number of unique configurations is the size of the set.
36 return visitedConfigurations.size;
37}
38
39// Count the number of bits set (1s) in the binary representation of the number.
40function countSetBits(number: number): number {
41 let count: number = 0;
42 while (number) {
43 count += number & 1;
44 number = number >> 1;
45 }
46 return count;
47}
48
Time and Space Complexity
Time Complexity
The main portion of the code is iterating through all possible combinations of the four light operations, which is done by looping from 0 to 1 << 4
(or 16
). This is a constant, as it does not depend on the input variables n
or presses
.
The .bit_count()
function on the mask
variable counts the number of set bits in mask's binary representation, and this is done in constant time, O(1), given modern computer architectures which support this operation natively.
The comparison operations and the bitwise operations inside the loop also take constant time.
Finally, for each valid mask, the code performs a reduction of the state space by only considering the first 6 lights and then shifting to consider the actual number (n
) of lights. This operation involves constant-time bitwise manipulation as well.
Taking all of the above into account, the overall time complexity of the function is O(1), since it is bounded by a constant number of operations that do not change with the size of the input.
Space Complexity
The space complexity is driven by the vis
set, which collects the unique states of the lights. In the worst-case scenario, every possible state of the lights is unique. Because the state space is reduced to min(n, 6)
, there are at most 2^6
(or 64
) unique states.
The vis
set will, therefore, contain at most 64
elements, regardless of the actual number of lights or presses. Hence, the space complexity is also O(1), because the amount of space required does not grow with the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the output of running the following function using the following tree as input?
1def serialize(root):
2 res = []
3 def dfs(root):
4 if not root:
5 res.append('x')
6 return
7 res.append(root.val)
8 dfs(root.left)
9 dfs(root.right)
10 dfs(root)
11 return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4 StringJoiner res = new StringJoiner(" ");
5 serializeDFS(root, res);
6 return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10 if (root == null) {
11 result.add("x");
12 return;
13 }
14 result.add(Integer.toString(root.val));
15 serializeDFS(root.left, result);
16 serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2 let res = [];
3 serialize_dfs(root, res);
4 return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8 if (!root) {
9 res.push("x");
10 return;
11 }
12 res.push(root.val);
13 serialize_dfs(root.left, res);
14 serialize_dfs(root.right, res);
15}
16
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.