Python, Straightforward with Explanation


  • 9

    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)
    

  • 0
    N

    Great solution!


Log in to reply
 

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