Intuitive solution


  • 1
    H

    First of all, this solution is not mine, I got it after studying cuiaoxiang's contest solution.

    This solution is based on the observation that any result from m > 4 can also be retrieved from a combination while m <= 4. This is because taking a same action twice is same as not taking it, while taking a same action three times is same as taking it one time, etc.
    While m <= 4, we should get 16 different combinations, and we can use a binary number to help us track whether we are taking operation 1), 2), 3) or 4)

    In this solution, we will check each of 16 combinations. In each combination, we firstly check how many operations will be taken. If the count > m, then we will not continue in current loop. If count <= m, then we also need to check if m%2 == count%2. Why? Please see comments in the code....
    After that, We can construct an array with len(n), because n <= 1000, this should not cause any boundary cases. We will apply each operation when the binary number has a 1 in the corresponding digit..
    We use a HashSet to catch all possible results and the size of result set should be our output.
    It costs me few hours to understand this solution, and I think it is more intuitive for me.....So here it is.

    public int flipLights(int n, int m) {
            HashSet<List<Boolean>> hs = new HashSet<>();
            
            for(int k = 0; k < 16; k++){
                //n bulbs
                Boolean[] curr = new Boolean[n];
                Arrays.fill(curr, false);
                int count = 0;
                
                for(int i = 0; i < 4; i++){
                    //check how many methods will be used in this loop
                    if( (k&(1<<i)) > 0 )  count++;  
                }
                
                //if we are going to pick more than m methods, then we skip current loop
                if(count > m) continue;
                //count < m will also work, since we can apply a same method multiple times
                //so that we need to check if m and count are both even or both odd.
                //duplicate operations + count = m
                //if count = 2, m = 3, then there is no way that we can use 3 operations to achieve the same effect of two operations
                //if count = 1, m = 3, then we can apply a method twice to achieve the same result
                //if count = 1, m = 2, then there is no way that we can use 1 operation to achieve the same effect of two operations
                //if count = 2 or count = 0, m = 2, we can just apply two methods or a method twice to achieve count = 2 or count = 0
                if( count%2 != m%2 ) continue;
                
                if( (k&1) > 0){
                    for(int i = 0; i < n; i++) curr[i] = !curr[i]; 
                }
                
                if( (k&2) > 0){
                    for(int i = 0; i < n; i+=2) curr[i] = !curr[i];
                }
                
                if( (k&4) > 0){
                    for(int i = 1; i < n; i+=2) curr[i] = !curr[i];
                }
                
                if( (k&8) > 0){
                    //3k+1, k = 0,1,2 => now we are 0 based, so it is 3k, k = 0,1,2
                    for(int i = 0; i < n; i += 3 ) curr[i] = !curr[i];
                }            
                List<Boolean> list = Arrays.asList(curr);
                hs.add(list);
            }
            
            //System.out.println(hs);
            return hs.size();
     }
    

Log in to reply
 

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