672. Bulb Switcher II
Problem Description
There is a room with n bulbs labeled from 1 to n that are all turned on initially, and four buttons on the wall. Each of the four buttons has a different functionality:
- Button 1: Flips the status of all the bulbs.
- Button 2: Flips the status of all the bulbs with even labels (i.e., 2, 4, ...).
- Button 3: Flips the status of all the bulbs with odd labels (i.e., 1, 3, ...).
- Button 4: Flips the status of all the bulbs with a label
j = 3k + 1wherek = 0, 1, 2, ...(i.e., 1, 4, 7, 10, ...).
You must press exactly presses buttons in total. Each time you press a button, it performs according to the rules above and presses the same button again counts as a different press.
Given the two integers n and presses, return the number of different possible states after performing all presses.
Examples:
Example 1:
Input: n = 1, presses = 1 Output: 2 Explanation: Status can be: [on], [off]
Example 2:
Input: n = 2, presses = 1 Output: 3 Explanation: Status can be: [on, on], [off, off], [on, off]
Example 3:
Input: n = 3, presses = 1 Output: 4 Explanation: Status can be: [off, on, off], [on, off, on], [off, off, off], [on, on, on]
Constraints:
- 1 ≤ n ≤ 1000
- 0 ≤ presses ≤ 1000
Python Solution
class Solution:
def flipLights(self, n: int, presses: int) -> int:
# For n >= 3, the pattern repeats every 6 bulbs
n = min(n, 6)
# If no presses, only one state possible
if presses == 0:
return 1
# For 1 press, we can get 2, 3, or 4 states depending on n
if presses == 1:
if n == 1:
return 2
elif n == 2:
return 3
else:
return 4
# For 2 presses, we can get all possible states
if presses == 2:
if n == 1:
return 2
elif n == 2:
return 4
else:
return 7
# For 3 or more presses, we can get all possible states
if presses >= 3:
if n == 1:
return 2
elif n == 2:
return 4
else:
return 8Alternative Solution (Using Set):
class Solution:
def flipLights(self, n: int, presses: int) -> int:
def flip(state, button):
new_state = list(state)
if button == 0: # All bulbs
for i in range(n):
new_state[i] = 1 - new_state[i]
elif button == 1: # Even bulbs
for i in range(1, n, 2):
new_state[i] = 1 - new_state[i]
elif button == 2: # Odd bulbs
for i in range(0, n, 2):
new_state[i] = 1 - new_state[i]
else: # 3k + 1 bulbs
for i in range(0, n, 3):
new_state[i] = 1 - new_state[i]
return tuple(new_state)
# Start with all bulbs on
initial = tuple([1] * n)
states = {initial}
# Apply presses
for _ in range(presses):
new_states = set()
for state in states:
for button in range(4):
new_states.add(flip(state, button))
states = new_states
return len(states)Implementation Notes:
- First solution uses mathematical pattern analysis
- Second solution simulates all possible states
- Time complexity: O(1) for first solution, O(4^presses) for second
- Space complexity: O(1) for first solution, O(2^n) for second
Java Solution
class Solution {
public int flipLights(int n, int presses) {
// For n >= 3, the pattern repeats every 6 bulbs
n = Math.min(n, 6);
// If no presses, only one state possible
if (presses == 0) {
return 1;
}
// For 1 press, we can get 2, 3, or 4 states depending on n
if (presses == 1) {
if (n == 1) {
return 2;
} else if (n == 2) {
return 3;
} else {
return 4;
}
}
// For 2 presses, we can get all possible states
if (presses == 2) {
if (n == 1) {
return 2;
} else if (n == 2) {
return 4;
} else {
return 7;
}
}
// For 3 or more presses, we can get all possible states
if (presses >= 3) {
if (n == 1) {
return 2;
} else if (n == 2) {
return 4;
} else {
return 8;
}
}
return 0;
}
}C++ Solution
class Solution {
public:
int flipLights(int n, int presses) {
// For n >= 3, the pattern repeats every 6 bulbs
n = min(n, 6);
// If no presses, only one state possible
if (presses == 0) {
return 1;
}
// For 1 press, we can get 2, 3, or 4 states depending on n
if (presses == 1) {
if (n == 1) {
return 2;
} else if (n == 2) {
return 3;
} else {
return 4;
}
}
// For 2 presses, we can get all possible states
if (presses == 2) {
if (n == 1) {
return 2;
} else if (n == 2) {
return 4;
} else {
return 7;
}
}
// For 3 or more presses, we can get all possible states
if (presses >= 3) {
if (n == 1) {
return 2;
} else if (n == 2) {
return 4;
} else {
return 8;
}
}
return 0;
}
};JavaScript Solution
/**
* @param {number} n
* @param {number} presses
* @return {number}
*/
var flipLights = function(n, presses) {
// For n >= 3, the pattern repeats every 6 bulbs
n = Math.min(n, 6);
// If no presses, only one state possible
if (presses === 0) {
return 1;
}
// For 1 press, we can get 2, 3, or 4 states depending on n
if (presses === 1) {
if (n === 1) {
return 2;
} else if (n === 2) {
return 3;
} else {
return 4;
}
}
// For 2 presses, we can get all possible states
if (presses === 2) {
if (n === 1) {
return 2;
} else if (n === 2) {
return 4;
} else {
return 7;
}
}
// For 3 or more presses, we can get all possible states
if (presses >= 3) {
if (n === 1) {
return 2;
} else if (n === 2) {
return 4;
} else {
return 8;
}
}
return 0;
};C# Solution
public class Solution {
public int FlipLights(int n, int presses) {
// For n >= 3, the pattern repeats every 6 bulbs
n = Math.Min(n, 6);
// If no presses, only one state possible
if (presses == 0) {
return 1;
}
// For 1 press, we can get 2, 3, or 4 states depending on n
if (presses == 1) {
if (n == 1) {
return 2;
} else if (n == 2) {
return 3;
} else {
return 4;
}
}
// For 2 presses, we can get all possible states
if (presses == 2) {
if (n == 1) {
return 2;
} else if (n == 2) {
return 4;
} else {
return 7;
}
}
// For 3 or more presses, we can get all possible states
if (presses >= 3) {
if (n == 1) {
return 2;
} else if (n == 2) {
return 4;
} else {
return 8;
}
}
return 0;
}
}Implementation Notes:
- Uses mathematical pattern analysis for efficiency
- Time complexity: O(1)
- Space complexity: O(1)
- Pattern repeats every 6 bulbs for n >= 3