Short and Clean Java O(1) Solution


  • 5

    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);
        }
    }
    

  • 2
    S

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


  • 0
    Z

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


  • 0
    K

    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.


  • 0

    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.


  • 0

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


  • 0

    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.


  • 0

    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 .


  • 0
    T

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


  • 0

    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?


  • 0

    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

Log in to reply
 

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