O(1)-time O(1)-space


  • 1
    0

    Why wasting space and time for such simple question ? :) Here's O(1) time / O(1) space solution which generates precise answer.
    This is based on the fact that fibonacci numbers series grows exponentially with the golden ratio as a base.

    Update: As tutubalin correctly pointed out this is actually O(log(n)) time because of pow()

    class Solution {
    public:
        int climbStairs(int n) {
            double sqrt5 = sqrt(5.0);
            double pfi = (1.0+sqrt5)/2;
            return (pow(pfi, n+1) - pow(-pfi, -(n+1)))/sqrt5 + 0.5;
        }
    };

  • 2
    T

    It is not true O(1), because pow operation is about O(log2 n).


  • 0
    0

    Yes, you're are absolutely right.


  • 0
    M

    I just cannot understand why the power is n+1 instead of n? Thank you.


  • 0
    M

    I understand now. Actually, the nth number in Binet's formula is F(n-1).


Log in to reply
 

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