Very easy to understand C++ with detailed explanation


  • 0

    At first this problem appears very intimidating. However, after walking through actual values, it is very simple. Below is my solution, and a step-by-step analysis for each part of code. Please feel free to provide comments to add/edit this post in order to provide better understanding for everyone. Thanks!

    class Solution {
    public:
        int flipLights(int n, int m) {
            
            if (m==0) { return 1; }
            
            if (n==1){
                if (m>=1) { return 2; }
            }
            if (n==2){
                if (m==1) { return 3; }
                if (m>=2) { return 4; }
            }
            if (n>=3){
                if (m==1) { return 4; }
                if (m==2) { return 7; }
                if (m>=3) { return 8; }
            }
            
            return 0; // invalid value for n or m
        }
    };
    

    STEP-BY-STEP ANALYSIS:

    Part 1: Description
    The first value to consider is m=0 operations. Regardless how many n lightbulbs there are with initial state ON, with 0 operations, all n lightbulbs will remain ON. Therefore, there is only one state ( all n lightbulbs ON ).

    Part 1: Code

    if (m==0) { return 1; }
    
    

    Part 2: Description
    Now consider one lightbulb (n=1). If we perform m=1 operation on that 1 lightbulb, then that 1 operation can be (flip all, flip odd, flip even, or flip 3k+1 [k=0, 3k+1=1]). The lightbulb's end state after 1 operation from [ flip all, flip odd, or flip 3k+1 ] is OFF. The end state after 1 operation from [ flip even ] is ON (since there are no even lightbulbs to flip, this single odd lightbulb remains ON). Therefore, there are 2 states for this 1 lightbulb after 1 operation. Below is a table summary of this lightbulb and its potential states. ON=1 and OFF=0.

    n=1
    lightbulb ID       1
    
    INIT_STATE:
    (initially ON)     1
    
    m=1
    OPERATIONS:
                       0 ( after 1 operation: flip all, odd, or 3k+1 )
                       1 ( after 1 operation: flip even )
    STATE_COUNT:
                       2 ( 0 or 1 )
    

    Now consider if there are any additional unique states which can be created with this one lightbulb with more than one operation. There are none. Either this one lightbulb is ON or OFF after m=1 operations. Any additional operations revert the lightbulb to a previous state, so there are no additional unique states created by any m>=1 operations.

    Part 2: Code

            if (n==1){
                if (m>=1) { return 2; }
            }
    

    Part 3: Description
    Next consider n=2 lightbulbs. The logic here is again the same as above, so I will skip the complete description and instead directly create an abridged table summary:

    n=2
    lightbulb ID       1 2
    
    INIT_STATE:
    (initially ON)     1 1
    
    m=1
    OPERATIONS:
                       0 0 ( after 1 operation: flip all )
                       0 1 ( after 1 operation: flip odd or 3k+1 )
                       1 0 ( after 1 operation: flip even )
    m=1
    STATE_COUNT:
                       3 ( 00 or 01 or 10 )
    
    m=2
    OPERATIONS:
                       0 0 ( after 2 operations: flip odd, flip even )
                       0 1 ( after 2 operations: flip all, flip even )
                       1 0 ( after 2 operations: flip all, flip odd )
                       1 1 ( after 2 operations: flip all, flip all )
    
    m=2
    STATE_COUNT:
                       4 ( 00 or 01 or 10 or 11 )
    

    There are multiple ways to arrive at the same lightbulb state with m=2 operations, but I did NOT list them all. This brevity is on purpose in order to help keep my verbose post as short and concise as possible. There is no need to list them all anyways because we are only interested in the amount of unique states in the end, NOT all the different ways which we arrived at those states.

    Now consider if there are any additional unique states which can be created with these two lightbulbs with more than two operations. There are none. Any additional operation m>=2 reverts these 2 lightbulbs to a previous state.

    Part 3: Code

            if (n==2){
                if (m==1) { return 3; }
                if (m>=2) { return 4; }
            }
    

    Part 4: Description
    Next consider n=3 lightbulbs. The logic here is again the same as above, so I will skip the complete description and instead directly create another abridged table summary:

    n=2
    lightbulb ID       1 2 3
    
    INIT_STATE:
    (initially ON)     1 1 1
    
    m=1
    OPERATIONS:
                       0 0 0 ( after 1 operation: flip all )
                       0 1 0 ( after 1 operation: flip odd )
                       0 1 1 ( after 1 operation: flip 3k+1 ) 
                       1 0 1 ( after 1 operation: flip even )
    m=1
    STATE_COUNT:
                       4 ( 000 or 010 or 011 or 101 )
    
    m=2
    OPERATIONS:
                       0 0 0 ( after 2 operations: flip odd, flip even )
                       0 0 1 ( after 2 operations: flip 3k+1, flip even )
                       0 1 0 ( after 2 operations: flip even, flip all )
                       1 0 0 ( after 2 operations: flip all, flip 3k+1 )
                       1 0 1 ( after 2 operations: flip odd, flip all )
                       1 1 0 ( after 2 operations: flip odd, flip 3k+1 )
                       1 1 1 ( after 2 operations: flip all, flip all )
    
    m=2
    STATE_COUNT:
                       7 ( 000 or 001 or 010 or 100 or 101 or 110 or 111 )
    
    m=3
    OPERATIONS:
                       ect...
                       ect...
                       ect...
    m=3
    STATE_COUNT:
                       8 ( 000 or 001 or 010 or 011 or 100 or 101 or 110 or 111 )
    

    Again, there are multiple ways to arrive at the same lightbulb state with m=2 and m=3 operations, but I did NOT list them all. This brevity is on purpose. Also, I did NOT explicitly write out all the different permutations for m=3, since they are all redundant states except for 011 which can be created with 3 operations [ flip 3k+1, flip odd, flip odd ].

    Again, consider if there are any additional unique states which can be created with these three lightbulbs with more than three operations. There are none. Any additional operation m>=3 reverts these 3 lightbulbs to a previous state. Also consider if there are more unique states which can be created with more than n=3 lightbulbs. There are none. Any additional amount of lightbulbs n>=3 does NOT create a new unique state. Instead repeated patterns are observed for lightbulbs that are even 2,4,6,etc (i.e. lightbulbs at positions 2(k+1), k=0,1,2... ), lightbulbs that are odd 1,3,5,etc (i.e. lightbulbs at positions 2k+1, k=0,1,2...), and lightbulbs at every 3rd position 1,4,7,10,etc ( i.e. lightbulbs at positions 3k+1, k=0,1,2...).

    Part 4: Code

            if (n>=3){
                if (m==1) { return 4; }
                if (m==2) { return 7; }
                if (m>=3) { return 8; }
            }
    

Log in to reply
 

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