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

  • 1

    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 {
        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

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

  • 0

    Yes, you're are absolutely right.

  • 0

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

  • 0

    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.