{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Fibonacci Number – Solution & Complexity

Interview solutions
/
Fibonacci Number

Solution Walkthrough

  1. Step 1: Understand the Sequence

    • Fibonacci starts with F(0) = 0 and F(1) = 1.
    • Every later value is the sum of the two previous values.
    • The input n asks for the 0-indexed value F(n).

  2. Step 2: Recursive Definition

    • The formula naturally translates into recursion.
    • However, plain recursion recomputes the same values many times.
    • That makes it exponential and too slow for larger n.
    def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

  3. Step 3: Keep Only the Last Two Values

    • To compute the next Fibonacci number, we only need the previous two.
    • Store them as a and b, representing consecutive Fibonacci values.
    • Repeatedly advance the pair until a reaches F(n).

  4. Step 4: Iterate Up to n

    • Start with a = 0 and b = 1.
    • Each loop moves from (F(i), F(i+1)) to (F(i+1), F(i+2)).
    • After n moves, a is the desired answer.
    def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

  5. Step 5: Final Solution and Complexity

    • The iterative solution avoids repeated work.
    • Time complexity is O(n).
    • Space complexity is O(1) because it stores only two integers.
    def fib(n: int) -> int:
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

FAQ

See also

Practice Fibonacci Number online (run code in the browser)Climbing Stairs solution (easy)Unique Paths solution (medium)Add Two Numbers solution (medium)Best Time to Buy and Sell Stock solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?