Java Solution


  • 0
    S

    Analysis the operations at first:

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

    We can found some rules:

    1. Do the same operations twice means we do nothing.
      1 + 1 = 2 + 2 = 3 + 3 = 4 + 4 = 0
    2. Operations 1, 2, 3 have the relationship:
      1 + 2 = 3, 1 + 3 = 2, 2 + 3 = 1
      e..g, we do operations 1 and 2, the result is the same as we just do operation 3.
    3. Operations 4 is independantly.

    Let's say n is the number of lights, m is the number of operations.
    When n <= 2, actually operation 4 equals to operation 3. When n = 3, op4 is different with any other operations. So if n > 3, we can just consider as n = 3.
    When m >= 3, whatever the operations are, the results cannot contains any two of operation [0, 1, 2, 3] because of the rule 2. e.g., if the operations are {1, 2, 4}, it would just equal to [3, 4].
    All the possible results can be listed : [0+4, 1+4, 2+4, 3+4, 0, 1, 2, 3]. So the result is 8.
    When m == 2, the operation 0+4 cannot happened. So the result is 7.

    public int flipLights(int n, int m) {
        int[][] tab = new int[][]{
                {1, 1, 1, 1},
                {1, 2, 2, 2},
                {1, 3, 4, 4},
                {1, 4, 7, 8}};
        if (n > 3) n = 3;
        if (m > 3) m = 3;
        return tab[n][m];
    }
    

Log in to reply
 

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