Simple thought process & code


  • 0
    S

    It seems that there are many states resulted from different operation sequences, however, if we look at operation sequences more closely(denoted 1,2,3,4 for each operation, 0 for "no change"):

    When m = 1:
    1=1,2=2,3=3,4=4

    When m = 2:
    11=0,12=3,13=2,14=14
    21=3,22=0,23=1,24=24
    31=2,32=1,33=0,34=34
    41=14,42=24,43=34,44=0

    so actually, when m = 2:
    0,1,2,3,4,14,24,34

    When m >=3:
    I try out when m=3, the sequences are also 0,1,2,3,4,14,24,34, after cancelling the same operations(like 12=3 etc). I then made a guess when m > 3 the case would be the same.

    And also list out some corner cases when n < 3 and m < 3, we get:

    class Solution {
    public:
        // 1,2,3,4,11=22=33=44,14,24,34
        int flipLights(int n, int m) 
        {
            if (!m) return 1;
            if (n == 1) return 2;
            if (n == 2 && m == 1) return 3;
            if (n == 2 && m >= 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.