# Python, Straightforward with Explanation

• 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)

return len(seen)
``````

• Great solution!

• 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.

great solution but I feel it's quite difficult to figure out the valid condition tho.

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