Fibonacci Number

Easy · Fibonacci roll. Real solution for this problem — same player as the hand-authored deep-dives.

Problem

Read the prompt, flip through the examples, then steal the idea.

LeetCode 509. Fibonacci Number. The copyrighted prompt is on LeetCode. This page is a working Fibonacci roll for this problem: editable input, Python, Go, and a step-by-step animation.

Constraints

—Player inputs are capped so the animation stays readable.
—Match LeetCode's own constraints when you submit there.

Examples

Input

n =: 2

Output

Solution

Python and Go. The walkthrough below runs this same code.

Approach 1Optimal▶ Animated

Two rolling variables

F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2). Roll a pair forward n times.

You only need the last two values. Recursing from the top would recompute the same suffixes.

Algorithm

If n < 2, return n.
a, b = 0, 1; then a, b = b, a+b for n-1 steps.
Return b.

Time: O(n)
Space: O(1)

Solution.py

1class Solution:2    def fib(self, n: int) -> int:3        if n < 2:4            return n5        a, b = 0, 16        for _ in range(2, n + 1):7            a, b = b, a + b8        return b

Watch this run

Interactive walkthrough

Playing “Two rolling variables”. Edit the input, hit Run, then scrub.

Approach: Two rolling variables

Loading animation…