{ }DevToolsDaily
ToolsInterview
Problems
New
CheatsheetsChat
New
BlogPricing
Ctrl + K

Fibonacci Number – Solution & Complexity

Interview solutions
/
Fibonacci Number

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. 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. 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. 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. 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)Best Time to Buy and Sell Stock solution (easy)Coin Change solution (medium)Edit Distance solution (hard)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsContact Us © Monkey SkatesHave kids?