Bulb Switcher II Problem


Description

LeetCode Problem 672.

There is a room with n bulbs labeled from 1 to n that all are turned on initially, and four buttons on the wall. Each of the four buttons has a different functionality where:

  • 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 + 1 where k = 0, 1, 2, … (i.e., 1, 4, 7, 10, …).

You must make exactly presses button presses in total. For each press, you may pick any of the four buttons to press.

Given the two integers n and presses, return the number of different possible statuses after performing all presses button presses.

Example 1:

1
2
3
4
5
Input: n = 1, presses = 1
Output: 2
Explanation: Status can be:
- [off] by pressing button 1
- [on] by pressing button 2

Example 2:

1
2
3
4
5
6
Input: n = 2, presses = 1
Output: 3
Explanation: Status can be:
- [off, off] by pressing button 1
- [on, off] by pressing button 2
- [off, on] by pressing button 3

Example 3:

1
2
3
4
5
6
7
Input: n = 3, presses = 1
Output: 4
Explanation: Status can be:
- [off, off, off] by pressing button 1
- [off, on, off] by pressing button 2
- [on, off, on] by pressing button 3
- [off, on, on] by pressing button 4

Example 4:

1
2
3
Input: n = 1, presses = 0
Output: 1
Explanation: Status can only be [on] since you cannot press any of the buttons.

Example 5:

1
2
3
4
5
Input: n = 1, presses = 2
Output: 2
Explanation: Status can be:
- [off] by pressing button 1 then button 1 again
- [on] by pressing button 1 then button 2

Constraints:

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


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    /**
    Observations:
    1) only the first 3 lights matter, since we can only switch (1) even (2) odd (3) (x = 1 MOD 3) lights
    2) all ops are commutative.
    3) there is only 8 states possible for all situations: All-on(111), 1(000), 2(010), 3(101), 4(011), 41(100), 42(110), 43(001)
    */
    int flipLights(int n, int p) {
    	// no presses, original state
        if (p == 0) return 1; 
        
        // constraint: (p > 0) : one light, binary states.
        if (n == 1) return 2; 

        // constraint: (p > 0 && n > 1) : one press, 
        // if (1) two lights -> all 2^2 but original state = 3 states 
        // (2) more than two lights -> 011, 010, 101, 000 = 4 states
        if (p == 1) return n > 2 ? 4 : 3; 

        // constraint: (p > 1 && n > 1) : two lights, multiple press, 4 states.
        if (n == 2) return 4; 

        // constraint: (p > 1 && n > 2) : if only two presses, 
        // can't be in 4(011) state -> 8-1 = 7
        return p == 2 ? 7 : 8; 
    }
};





Related Posts

Score After Flipping Matrix Problem

LeetCode 861. You are given an m x n binary...

Chalkboard Xor Game Problem

LeetCode 810. You are given an array of integers nums...

Bitwise ORs Of Subarrays Problem

LeetCode 898. We have an array arr of non-negative integers....

Binary Gap Problem

LeetCode 868. Given a positive integer n, find and return...

K-Th Symbol In Grammar Problem

LeetCode 779. We build a table of n rows (1-indexed)....