Python problem 12 of 30

Fast Fibonacci

Python
Easy

The naive recursive Fibonacci makes an exponential number of calls. Write fib(n) that returns the nth Fibonacci number (with fib(0) = 0 and fib(1) = 1) in O(n) time.

fib(10)   # 55
fib(50)   # 12586269025

Show hint

You only ever need the last two values.

Show solution

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Tuple assignment updates both values at once, so there is no temporary variable. O(n) time, O(1) space. Python integers never overflow, so fib(1000) works too.

Want a problem like this every day? See today's problem and keep a streak going.