Approach #1: Brute Force with Optimizations [Accepted]
Intuition
Naively, the number of operations is $$4^m$$, and the number of lightstates is $$2^n$$. These are way too big, so we focus on heuristics that can reduce the size of these spaces that we want to search on.
Algorithm
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. So we only care about the quantity of each operation.
Secondly, when it comes to the state of the lights, 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)
, but not all of them necessarily occur. cand
occurs only if there is some f
with sum(f) == m
and cand[i] = f[i] % 2
.
The necessary and sufficient condition to find such an f
is sum(cand) % 2 == m % 2 and sum(cand) <= m
. With exactly m
operations, we must spend sum(cand)
operations doing the operations indicated by cand
; then as long as we have an even number of operations left over, we can keep doing operation 1; and if we don't have an even number of operations left over, we can't make cand
as desired.
Also, we can set n = min(n, 6)
. We only need to care about the first 6 lights, as the 6k+i
th light is equal to the i
th light. This is because the first operation repeats every 1 light, the second and third operations repeat every 2 lights, and the fourth operation repeats every 3 lights; hence, no matter what operations are applied, the lights will repeat every $\text{lcm}(1, 2, 2, 3) = 6$ lights.
Java
class Solution {
public int flipLights(int n, int m) {
n = Math.min(n, 6);
Set<Integer> seen = new HashSet<Integer>();
for (int cand = 0; cand < 1<<4; cand++) {
if (Integer.bitCount(cand) <= m &&
Integer.bitCount(cand) % 2 == m % 2) {
int lights = 0b111111;
if ((cand>>0) %2 > 0) lights ^= 0b111111;
if ((cand>>1) %2 > 0) lights ^= 0b010101;
if ((cand>>2) %2 > 0) lights ^= 0b101010;
if ((cand>>3) %2 > 0) lights ^= 0b100100;
seen.add(lights >> (6n));
}
}
return seen.size();
}
}
Python
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:
lights = []
for i in xrange(min(n, 6)):
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
lights.append(light)
seen.add(tuple(lights))
return len(seen)
Complexity Analysis

Time Complexity: $$O(1)$$. For each of 16 possibilities for
cand
, we do $$O(min(n, 6)) = O(1)$$ work. 
Space Complexity: $$O(1)$$. The size of
seen
is bounded by 16  one for each candidate sequence of residuescand
.
Approach #2: Mathematical [Accepted]
Intuition
As in Approach #1, we only need to consider $$n \leq 6$$. Also, when $$m \geq 3$$, all candidate residues cand
are valid as defined in Approach #1. Thus, we only need to consider the space $$m \leq 3, n \leq 6$$  a space small enough to brute force.
Algorithm
Actually, we may take n = min(n, 3)
. If the operations are a, b, c, d
, then modulo 2:
 Light 1 = Light 7 = ... =
1 + a + c + d
 Light 2 = Light 8 = ... =
1 + a + b
 Light 3 = Light 9 = ... =
1 + a + c
 Light 4 = Light 10 = ... =
1 + a + b + d
 Light 5 = Light 11 = ... =
1 + a + c
 Light 6 = Light 12 = ... =
1 + a + b
So that (modulo 2):
 Light 4 = (Light 1) + (Light 2) + (Light 3)
 Light 5 = Light 3, and
 Light 6 = Light 2.
which shows that knowing the first 3 lights is enough to determine all the remaining lights in the sequence.
Now, we can do casework on m
. The transitions made by the operations a, b, c, d
are to XOR by (1, 1, 1)
, (0, 1, 0)
, (1, 0, 1)
, or (1, 0, 0)
respectively.
 If
m = 0
, there is only one state(1, 1, 1)
.  If
m = 1
, then we could get(0, 0, 0), (1, 0, 1), (0, 1, 0), (0, 1, 1)
.  If
m = 2
, with some effort we can get all 8 possibilities except(0, 1, 1)
.  If
m = 3
, we can get every possibility.
This reduced the problem to knowing the answer for m <= 3, n <= 3
. The final answer is shown below.
Java
class Solution {
public int flipLights(int n, int m) {
if (m == 0) return 1;
if (n == 1) return 2;
if (n == 2) return m == 1 ? 3 : 4;
return m == 1 ? 4 : m == 2 ? 7 : 8;
}
}
Complexity Analysis
 Time and Space Complexity: $$O(1)$$.