My O(n/2) solution in C++


  • 0
    Z
    class Solution {
    public:
        int climbStairs(int n) {
            if(n <= 3) return n;
            int maxTwos = n /2;
            int result = 1;
            int prev = n -1;
            result += n-1;
            for(int i=2; i<= maxTwos; i++){
                long long  lastTwos = i-1;
                long long lastOnes = n - (2* (i-1));
                int current = prev * (lastOnes * (lastOnes-1))/((lastTwos + lastOnes)*(lastTwos +1));
                result += current;
                prev = current;
            }
            return result;
        }
    };

Log in to reply
 

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