Java O(1)


  • 19
    W

    We only need to consider special cases which n<=2 and m < 3. When n >2 and m >=3, the result is 8.
    The four buttons:

    1. Flip all the lights.
    2. Flip lights with even numbers.
    3. Flip lights with odd numbers.
    4. Flip lights with (3k + 1) numbers, k = 0, 1, 2, ...

    If we use button 1 and 2, it equals to use button 3.
    Similarly...

    1 + 2 --> 3, 1 + 3 --> 2, 2 + 3 --> 1
    So, there are only 8 cases.

    All_on, 1, 2, 3, 4, 1+4, 2+4, 3+4

    And we can get all the cases, when n>2 and m>=3.

    class Solution {
        public int flipLights(int n, int m) {
            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;
            if(m>=3) return 8;
            return 8;
        }
    }
    

  • 2
    L

    Thanks for your smart solution! The following is my attempt to understand it.

    The four buttons correspond to four kinds of numbers:
    x % 2 == 1 && x % 3 == 1, such as x == 1;
    x % 2 == 1 && x % 3 != 1, such as x == 3;
    x % 2 == 0 && x % 3 == 1, such as x == 4;
    x % 2 == 0 && x % 3 != 1, such as x == 2.

    There are eight independent button operations (suppose the initial status is on, on, on, on) : 1 (off, off, off, off), 2 (on, off, on, off), 3 (off, on, off, on), 4 (off, on, on, off), 1 + 4 (on, off, off, on), 2 + 4 (off, off, on, on), 3 + 4 (on, on, off, off), 1 + 2 + 3 == 3 + 3 (on, on, on, on), because 1 + 2 == 3, 2 + 3 == 1, 1 + 3 == 2, 1 + 2 + 4 == 3 + 4, 2 + 3 + 4 == 1 + 4,1 + 3 + 4 == 2 + 4, 1 + 2 + 3 + 4 == 3 + 3 + 4 == 4. The first operation changes all bulbs simultaneously, the eighth brings no change at all, the rest six operations always flip two bulbs together, so there are only three independent bulbs among the four kinds. We only need analyze cases for n = 1, 2, 3.

    When m == 0, nothing happens, there is only one status;

    when n == 1, the bulb can be kept "on" as a result of button operation 2, or switched "off" as a result of operation 1 or 3 or 4. Operation 2 equals operation 1 plus operation 3, operation 3 equals the combination of operation 1 and 2, operation 1 is equal to operation 2 plus 3. Therefore we can get the same status after both odd and even operations. Case n == 1 always yields 2;

    when n == 2, there are four possible status, "on, off" == operation 2 or 1 + 3, "off, on" == 3 or 1 + 2, "off, off" == 1 or 2 + 3, "on, on" == 1 + 1 == 2 + 3 + 1 == 1 + 3 + 3 + 1 == ... or 2 + 2 or 3 + 3 or 4 + 4. Except status "on, on" which can be reached only after 2 or more operations, all the rest status can be obtained through both odd and even operations;

    When n == 3, eight distinct status are possible. Using the same trick, we can find there are only two special cases: m == 1 and m == 2, all the other cases yield the same result 8.


  • 0

    Can you explain the second last condition ?


  • 2
    L

    For n == 3, there are 8 status:

    on, on, on == 1 + 1 = (2 + 3) + 1 = (1 + 3) + 3 + 1 = (2 + 3) + 3 +3 + 1 == ...
    It can be obtained when the number of operations >= 2, since we can decompose 1/2/3 to two combined operations;

    on, on, off == 3 + 4 == (1 + 2) + 4 == (2 + 3) + 2 + 4 = (1 + 3) + 3 + 2 + 4 == ... It can be obtained for m >= 2;

    on, off, on == 2 == 1 + 3 == (2 + 3) + 3 == ... It can be obtained for m >= 1;

    on, off, off == 1 + 4 == (2 + 3) + 4 == ... It can be obtained for m >= 2;

    off, on, on == 4 == (1 + 1) + 4 == (2 + 3) + 1 + 4 == (1 + 3) + 3 + 1 + 4 == ... It can be obtained for m == 1 or m >= 3;

    off, on, off == 3 == 1 + 2 == (2 + 3) + 2 == ... It can be obtained for m >= 1;

    off, off, on == 2 + 4 == (1 + 3) + 4 == (2 + 3) + 3 + 4 == (1 + 3) + 3 + 3 + 4 == ... It can be obtained for m >= 2;

    off, off, off == 1 == 2 + 3 == (1 + 3) + 3 == ... It can be obtained for m >= 1.

    In summary, for the case of n == 3, when m == 1, four status can be reached, when m == 2, seven status except "off, on, on" can be obtained,
    when m >= 3, all eight status can be obtained.

    Actually, these eight status can be represented by binary numbers from 0 to 7, the four operations can be represented by applying xor operation between a status and binary numbers 111, 010, 101, 100. I wonder if there is a more general solution using bit manipulation.


  • 1
    X

    @lakeshore1986
    Hi, your explanation is very detailed, thank you! But I don't think this observation is right:

    since a bulb with an index > 3 only repeats the behaviors of the bulb with index = n % 3.

    bulb:  1  2  3  4  5  6  7  8  9  10 11 12 13
    btn_1  !  !  !  !  !  !  !  !  !  !  !  !  !
    btn_2     !     !     !     !     !     !
    btn_3  !     !     !     !     !     !     !
    btn_4  !        !        !        !        !
    

    So we can see bulb with number 7, 13 ... are the same with number 1, which is n%3;
    bulb with number 6, 8, 12 ... are the same with number 2, see, not n%3;
    bulb with number 5, 9, 11... are the same with number 3, also not n%3;
    bulb with number 10, ... are the same with number 4, also not n%3;

    So a better saying might be:

    the status of bulbs [1, 2, 3, 4] simply determines the status of all n bulbs (n > 4).

    Please correct me if I make it wrong, thank you.


  • 1
    L

    Thanks for pointing this out! you're right.

    @XiaoweiLu said in Java O(1):

    @lakeshore1986
    Hi, your explanation is very detailed, thank you! But I don't think this observation is right:

    since a bulb with an index > 3 only repeats the behaviors of the bulb with index = n % 3.

    bulb:  1  2  3  4  5  6  7  8  9  10 11 12 13
    btn_1  !  !  !  !  !  !  !  !  !  !  !  !  !
    btn_2     !     !     !     !     !     !
    btn_3  !     !     !     !     !     !     !
    btn_4  !        !        !        !        !
    

    So we can see bulb with number 7, 13 ... are the same with number 1, which is n%3;
    bulb with number 6, 8, 12 ... are the same with number 2, see, not n%3;
    bulb with number 5, 9, 11... are the same with number 3, also not n%3;
    bulb with number 10, ... are the same with number 4, also not n%3;

    So a better saying might be:

    the status of bulbs [1, 2, 3, 4] simply determines the status of all n bulbs (n > 4).

    Please correct me if I make it wrong, thank you.


  • 0

    This code is wrong. Fails for example n=0, m=1. Correct answer is 1. You return 4. Judge expects 3. Sigh. No idea why the judge didn't include all cases for n and m up to let's say 20.


  • 1

    @XiaoweiLu said in Java O(1):

    the status of bulbs [1, 2, 3, 4] simply determines the status of all n bulbs (n > 4).

    Already the bulbs [1, 2, 3] determine the status of all others. Bulb 4 is determined by the bulbs 1, 2 and 3 (just xor them).


  • 0
    X

    @StefanPochmann Yes you are right. I didn't observe that. So only the first three bulbs matter.


Log in to reply
 

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