JAVA O(1) solution detail explaination


  • 0
    X

    for four switches , there are 16 combinations:
    0000
    0001
    0010
    0011
    ....
    1110
    1111

    as @woshifumingyuan have explained 1+2 = 3, 1+3 = 2, 2+3 = 1

    so :

    1. all on 0000 = 1110
    2. turn on 4 0001 = 1111
    3. turn on 3 0010 = 1100
    4. turn on 2 0100 = 1010
      5.turn on 2+4 0101 = 1011
      6.turn on 1 0110 = 1000
      7.turn on 1+4 0111 = 1001
      8.turn on 1+4 0011 = 1101
      totally, there are only 8 cases. we reduce 16 cases into 8 cases.

    but n <= 2 and m < 3 cases needed to be considered individually because:

    1. when there is only one light, there will be two status: on and off
    2. when there are two lights:
      1. m = 1, only have 3 status: off off, off, on, off on
      2 . m >= 2, will have four status: off off, off on, on off, off off.
    3. when n > 2 && m == 1, will have four status: 0001, 0010, 0100, 1000
    4. when n > 2 && m == 2, will have 7 status: 0000, 1100, 1010, 0101, 0110, 1001, 0001
    5. other cases will have 8 status.
    class Solution {
        public int flipLights(int n, int m) {
            if (n == 0) return 0;
            if (m == 0) return 1;
            if (n == 1) return 2;
            if (n == 2 && m == 1) return 3;
            if (n == 2) return 4;
            if (m == 1) return 4;
            if (m == 2) return 7;
           return 8;
        }
    }
    

Log in to reply
 

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