Short and Clean Java O(1) Solution

• `1`: light is on
`0`: light is off

n == 1

Only 2 possibilities: `1` and `0`.

n == 2

After one operation, it has only 3 possibilities: `00`, `10` and `01`.
After two and more operations, it has only 4 possibilities: `11`, `10`, `01` and `00`.

n == 3

After one operation, it has only 4 possibilities: `000`, `101`, `010` and `011`.
After two operations, it has 7 possibilities: `111`,`101`,`010`,`100`,`000`,`001` and `110`.
After three and more operations, it has 8 possibilities, plus `011` on above case.

n >= 4

After one operation, it has only 4 possibilities: `0000`, `1010`, `0101` and `0110`.
After two or more operations: it has 8 possibilities, `1111`,`1010`,`0101`,`0111`,`0000`,`0011`, `1100` and `1001`.

``````class Solution {
public int flipLights(int n, int m) {
if (m == 0) return 1;
if (n <= 0 || m < 0) return 0;

if (n == 1) return 2;
else if (n == 2) return (m == 1) ? 3 : 4;
else return (m == 1) ? 4 : ((m == 2) ? 7 : 8);
}
}
``````

• This is smart, only think about the first four bits.

• @super62650 What if the number of bulbs are not 4n?

• Why are only 7 operations possible for n=3 and m=2?
We can reach 011 when n=3 and m=1. By flipping all bulbs in 011 can't we get 100?
Correct me if I am wrong.

• Edit: fixed now
@kartymak Already m=1 is wrong, we can't have 111 and 011 after one move. I guess he got confused about his own (missing!) definition of what his "1" and "0" mean.

• Hi @kartymak & @StefanPochmann , thanks for the correction, `100` is a valid result for {n: 3, m: 2}.

I got it wrong when I copied the truth table of {n: 3, m: 1} from manuscript, which leads to an invalid result `011` for {n: 3, m: 2}.

• Edit: fixed now
@zhipj You made the same mistake in "n >= 4". And your "n == 3" is now incompatible to your "n == 2". In "n == 2", clearly "1" means "light changed". But in "n == 3", clearly "1" means "light on". You'd better make up your mind, decide what you want it to mean. And say it.

• Oops, the same issue for `m == 2` and `m == 4`, fixed it and claimed it on top of the post, I never thought that `1` would mean "light changed", I mistook `00...0` with `11...1`. Thanks @StefanPochmann .

• @zhipeng5 The first 4 bits uniquely determines the bits of all rest.

• Something is still wrong. How do you think n>=4 can have 0111 after two moves when n==3 can't have 011 after two moves?

• I think n==3 and n>=4 is not fully correct.

when n==3 and m==2, possible states are as below
Initial state : 111

1. Flip All : 000
2. Flip even : 101
3. Flip odd : 010
4. 3k + 1: 011
5. Combination of 1 and 4: 100
6. Combination of 2 and 4: 001
7. Combination of 3 and 4: 110

Similarly,
When n==4 and m==2, possible states are as below
Initial state : 1111

1. Flip All : 0000
2. Flip even : 1010
3. Flip odd : 0101
4. 3k + 1: 0110
5. Combination of 1 and 4: 1001
6. Combination of 2 and 4: 0011
7. Combination of 3 and 4: 1100

In both the above cases, the initial state cant be reached. But, initial state can be reached if m >= 3 and hence m >= 3 has 8 states

example: when n == 4
Initial state: 1111

1. Flip even: 1010
2. Flip odd: 0000
3. Flip All: 1111

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