# Easy to understand Java BFS solution O(m)

• I see all are math based solutions and it is O(1).
Here is my BFS solution to count all potential status for n bulb after m operations.

``````public int flipLights(int n, int m) {
n = n <= 6? n: (n % 6 + 6);

Set<Integer> visited = new HashSet<>();
int init = (1 << n) - 1;
queue.offer(init);
for (int i=0; i<m; i++) {
int size = queue.size();
visited.clear();
for (int k=0; k<size; k++) {
int s = queue.poll();
int[] next = new int[] {flipAll(s, n),
flipEven(s, n), flipOdd(s, n), flip3k1(s, n)};
for (int s1: next) {
if (!visited.contains(s1)) {
queue.offer(s1);
}
}
}
}
return queue.size();
}

private int flipAll(int s, int n) {
int x = (1 << n) - 1;
return s ^ x;
}

private int flipEven(int s, int n) {
for (int i=0; i<n; i+=2) {
s ^= 1 << i;
}
return s;
}

private int flipOdd(int s, int n) {
for (int i=1; i<n; i+=2) {
s ^= 1 << i;
}
return s;
}

private int flip3k1(int s, int n) {
for (int i=0; i<n; i+=3) {
s ^= 1 << i;
}
return s;
}
``````

• Why is it O(m)? Isn't it O(m*queue_size) because queue_size is not a constant?

• An integer is 32-bit but n fits in range [0 1000], how could you use an integer to represent the status of 1000 bulb?

• @MinJiang
If you look at the operations, they are operations modulo 2 and 3. So you only need consider a sequence of 6 bulbs. Every 6 bulbs in a row share same states.

• @richdalgo Queue size has a fixed upper bound. You can refer the O(1) solution.

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