Suppose we did
f of the first operation,
f of the second,
f of the third, and
f 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.
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
sum(f) == m and
cand[i] = f[i] % 2.
Also, as the sequence of lights definitely repeats every 6 lights, we could replace
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 light ^= cand and i % 2 light ^= cand and i % 2 == 0 light ^= cand and i % 3 == 0 A.append(light) seen.add(tuple(A)) return len(seen)