672.md

672. Bulb Switcher II

There is a room with n lights which are turned on initially and 4 buttons on the wall. After performing exactly m unknown operations towards buttons, you need to return how many different kinds of status of the n lights could be.

Suppose n lights are labeled as number [1, 2, 3 ..., n], function of these 4 buttons are given below:

Flip all the lights.
Flip lights with even numbers.
Flip lights with odd numbers.
Flip lights with (3k + 1) numbers, k = 0, 1, 2, ...
Example 1:
Input: n = 1, m = 1.
Output: 2
Explanation: Status can be: [on], [off]
Example 2:
Input: n = 2, m = 1.
Output: 3
Explanation: Status can be: [on, off], [off, on], [off, off]
Example 3:
Input: n = 3, m = 1.
Output: 4
Explanation: Status can be: [off, on, off], [on, off, on], [off, off, off], [off, on, on].
Note: n and m both fit in range [0, 1000].

my thoughts:

1. the operations will eventually repeat the result, just write case by case till it hits 8 (the max outcome cout)

my solution:

**********35ms
class Solution(object):
    def flipLights(self, n, m):
        """
        :type n: int
        :type m: int
        :rtype: int
        """
        
        if n == 0:
            return 0
        if m == 0:
            return 1
        if m == 1:
            return n+1 if n+1<4 else 4
        
        if n < 3:
            return 2**n
        
        if m == 2:
            return 7
        
        return 8

my comments:

Read question more carefully. it says 'exactly m operations' so when m = 2, we cannot produce the result of doing button 4 only once.

from other ppl's solution:

1. a solution I do not quite understand yet:
Suppose we did f[0] of the first operation, f[1] of the second, f[2] of the third, and f[3] of the fourth, where sum(f) == m.

First, all these operations commute: doing operation A followed by operation B yields the same result as doing operation B followed by operation A. Also, doing operation A followed by operation A again is the same as doing nothing. So really, we only needed to know the residues cand[i] = f[i] % 2. There are only 16 different possibilities for the residues in total, so we can try them all.

We’ll loop cand through all 16 possibilities (0, 0, 0, 0), (0, 0, 0, 1), ..., (1, 1, 1, 1). A necessary and sufficient condition for cand to be valid is that sum(cand) % 2 == m % 2 and sum(cand) <= m, as only when these conditions are satisfied can we find some f with sum(f) == m and cand[i] = f[i] % 2.

Also, as the sequence of lights definitely repeats every 6 lights, we could replace n with min(n, 6). Actually, we could replace it with min(n, 3), as those lights are representative: that is, knowing the first 3 lights is enough to reconstruct what the next 3 lights will be. If the first 3 lights are X, Y, Z, then with a little effort we can prove the next 3 lights will be (X^Y^Z), Z, Y.

def flipLights(self, n, m):
    seen = set()
    for cand in itertools.product((0, 1), repeat = 4):
        if sum(cand) % 2 == m % 2 and sum(cand) <= m:
            A = []
            for i in xrange(min(n, 3)):
                light = 1
                light ^= cand[0]
                light ^= cand[1] and i % 2
                light ^= cand[2] and i % 2 == 0
                light ^= cand[3] and i % 3 == 0
                A.append(light)
            seen.add(tuple(A))

    return len(seen)