Problem statement

https://leetcode.com/problems/bulb-switcher-ii/

Solution

What we can note, that we always have period 6 in our data: so we can just consider first 6 bulbs. Then just let consider set of seen states and update it, there will be no more than 64 states. We use binary masks: 63 = 111111, 36 = 100100, 42 = 101010 and 21 = 010101 and then we cut last bits, using >>(6-n)<<(6-n) trick.

Complexity

Time and space complexity is O(1).

Code

class Solution:
    def flipLights(self, n, m):
        if n > 6: n = 6
        states = set([0])
        mods = [21, 42, 36, 63]
        for i in range(m):
            states_new = set()
            for state, mod in product(states, mods):
                states_new.add(state^mod)
            if len(states) == len(states_new): break
            states = states_new
        
        return len(set([i>>(6-n)<<(6-n) for i in states]))

Remark

Actually, we can improve it and show that all state will be defined not by 6, but by 3 first bulbs. Also we can just precalculate all options:

  1. If n = 1, then we have 1 status for m = 0 and 2 for m > 0.
  2. if n = 2, then we have answer 1 for m = 0, 3 for m = 1 and 4 for m > 1.
  3. if n >= 3, then we have 1 for m = 0, 4 for m = 1, 7 for m = 2 and 8 for m >= 3.

Time and space complexity is O(1).