Simple O(n) time, O(1) space C++ solution


  • 0
    J
     int numWays(int n, int k) {
            // special cases
            if(k == 0 || n == 0)  return 0;
            if(k == 1)  return n <= 2;  
            if(n == 1)  return k;
            
    // f1 : for current number of posts, number of ways ended by 2 diff colors 
    // f2 : for current number of posts, number of ways ended by 2 same colors 
           
            // start from 2 posts
            int f1 = k * ( k - 1 ), f2 = k, f = k * k, cnt = 2;
            
            while(cnt++ < n){
                f2 = f1;
                f1 = f * ( k - 1 );
                f = f1 + f2;
            }        
            return f;
        }  
    

Log in to reply
 

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