Lazy, generalizable O(1) python solution with explanation


  • 0
    E

    Operations:

    1. toggle all
    2. toggle even
    3. toggle odd
    4. toggle 1+3k

    Since each operation always toggles the same set of lights, each operation cancels itself out when applied twice (or an even number of times). Thus we can consider each operation to be like a state, which can be "ON" or "OFF". There are 4 individual "operation states", which combined yield an upper bound of 2^4 "bulb states" (since "bulb states" are a function of the operation states).

    But since operation 1 (toggle all) is equivalent to operations 2+3, (odd+even) it is redundant unless constrained by # of operations, there are only 3 unique operations and 2^3 = 8 possible "operation states". (We can only reach 4 unique "bulb states" using any number of operations 1,2,3, i.e. the bulb states ["all off", "even on", "odd on", "all on"]), .

    Since we can reach any of the 2^3 "operation states" in at most 3 operations, we are free to limit m to a max of 3, and consider only the arity of values of m >3 (since we need exactly, not at least m operations).

    But, again since operations 2+3 (even + odd) are equivalent to operation 1 (toggle all), we can also ignore the arity for m>3 values, since we can always change arity of m by changing operation 1 with 2+3 or viceversa.

    Finally, for each of the unique combination of the 2^3 "operation states", we can find the 8 sets of integers which it affects (i.e. all the integers in this set will have the same value):

    • : {}
    • 1: odd integers
    • 2: even integers
    • 1+2: all integers
    • 3: integers n s.t. n%3==1
    • 3+1 integers n s.t. n%3==1 and n%2==1
    • 3+2: integers n s.t. n%3==1 and n%2==0
    • 3+1+2: integers n s.t. n%3!=1

    Since when n=3, there is at least one integer represented in each of the sets above, we can restrict n to a max 3 (any higher index will be in an equivalence class represented by one of the numbers <=3 regardless of which "operation states" are "ON").

    Since we can limit both n and m to a constant, we can do an exhaustive search in constant time to find the number of unique bulb-states:

    class Solution(object):
            
        def flipLights(self, n, m):
            """
            :type n: int
            :type m: int
            :rtype: int
            """
            states=set()
            n=min(3,n)
            m=min(m,3)
            def flips(op, i):
                return op==0 or\
                        (op==1 and i%2==1) or\
                        (op==2 and i%2==0) or\
                        (op==3 and i%3==0)
            
            for B in xrange(1<<4):
                nflips=sum((B>>i)&1 for i in xrange(1<<4))
                if nflips>m or nflips%2 != m%2:
                    continue
                curr=""
                for i in xrange(n):
                    d=sum(flips(op, i) for op in xrange(4) if (B>>op)&1)
                    curr+="01"[d%2]
                states.add(curr)
                    
            return len(states)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.