Start learning free

LESSON 188 OF 414 · LOOPS - CHALLENGES

Fibonacci in Rust: O(n) Time and O(1) Space with a Loop

Practice Read the full explanation

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Given n, calculate and return F(n).


Example 1:

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2:

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Example 3:

Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

Note:

Your algorithm should run in O(n) time and use O(1) space.


Hints:


As we compute each new Fibonacci number as the sum of the previous two, we will use 2 variables prev and curr to store the last two computed Fibonacci numbers at each moment of time. We should initialize prev with 0(F(0)) and curr with 1(F(1)).

There are n - 1 more numbers to be computed: F(2), F(3), ..., F(n). Let's write a for loop that iterates with a variable i through the values 2 to n. Inside this loop, we should compute the new Fibonacci number (F(i)) and update the variables prev and curr.

At the beginning of each iteration, F(i - 2) is stored in prev, F(i - 1) is stored in curr and we want to compute F(i). At the end of the iteration, we want prev to store F(i - 1) and curr to store F(i).
So we can use another variable next to store prev + curr and then we can assign curr to prev (prev = curr) and next to curr (curr = next).

After the loop finishes execution, the answer (F(n)) lies in curr.
Also, don't forget to treat the special cases n = 0 and n = 1 (when n < 2, the answer is n itself) at the beginning of the algorithm.

STEP 1 OF 6
    Ctrl + Enter to check

    RUST · LOOPS - CHALLENGES

    Fibonacci in Rust, explained

    Problem overview

    The function fibonacci takes an i32 called n and returns F(n), the n-th Fibonacci number. The sequence starts F(0) = 0 and F(1) = 1, and every later number is the sum of the two before it: F(n) = F(n - 1) + F(n - 2).

    So the sequence runs 0, 1, 1, 2, 3, 5, 8, 13 and so on. For n = 2 the answer is 1, for n = 3 it is 2, and for n = 4 it is 3. The statement asks for O(n) time and O(1) extra space.

    Approach: remember only the last two numbers

    The definition reads like a recursive function, and writing it that way is the obvious first attempt. It is slow, though: F(n) calls F(n - 1) and F(n - 2), which both call their own smaller versions, so the same values are recomputed again and again and the work roughly multiplies with each step up in n.

    To see the cost, count the calls of a recursive version: computing F(30) makes 2,692,537 calls to produce an answer of 832,040. A loop needs 29 additions for the same input.

    The faster idea is to build the sequence from the bottom. To get F(i) you need only F(i - 1) and F(i - 2), and nothing older. So two variables, prev and curr, are enough. Start from F(0) and F(1) and slide this two-number window forward one position at a time until curr holds F(n). That does n - 1 additions and stores two integers, which meets the O(n) and O(1) budget.

    Step by step

    1. Handle the base cases. If n is less than 2, return n itself: F(0) is 0 and F(1) is 1. One comparison covers both.
    2. Declare prev and curr as let mut variables of type i32, set to 0 and 1. At the start they hold F(0) and F(1). At the start of each iteration for index i, prev holds F(i - 2) and curr holds F(i - 1).
    3. Loop from 2 to n inclusive with 2..=n. The numbers still missing are F(2) through F(n), and the = makes the range include n.
    4. Compute next, the sum of curr and prev. This is F(i).
    5. Slide the window. Assign curr to prev first, then next to curr. The order matters: the old curr must be copied into prev before curr is overwritten. Starting from prev = 1 and curr = 2, the update gives prev = 2 and curr = 3.
    6. Return curr. After the last iteration it holds F(n).

    Tracing n = 4: the loop starts with prev = 0 and curr = 1. For i = 2 the new value is 1, giving prev = 1 and curr = 1. For i = 3 it is 2, giving prev = 1 and curr = 2. For i = 4 it is 3, giving prev = 2 and curr = 3. The function returns 3.

    The solution in Rust

    impl Solution {
    fn fibonacci(n: i32) -> i32 {
        if n < 2 {
            return n;
        }
        let mut prev: i32 = 0;
        let mut curr: i32 = 1;
        for i in 2..=n {
            let next: i32 = curr + prev;
            prev = curr;
            curr = next;
        }
        return curr;
    }
}

    Rust details worth knowing:

    • Bindings are immutable by default. prev and curr change on every iteration, so they need mut. next is created fresh in each iteration and never changes, so a plain let is right.
    • Inclusive and exclusive ranges. 2..n stops before n, while 2..=n includes it. Using the wrong one makes the answer F(n - 1). When n is 2 the range 2..=2 holds one value, so the loop runs once.
    • The loop variable is never read. The loop only counts iterations, so the compiler warns that i is unused. Writing _ instead of i would silence it. The code is correct either way.
    • Copying is cheap. prev = curr copies an i32; there is no ownership issue because integers implement Copy.
    • Early return. The return n; inside the if leaves the function immediately. The final return curr; could also be written as just curr, with no semicolon.

    Complexity

    Time: O(n). The loop runs n - 1 times and each iteration does a fixed amount of work: one addition and two assignments. Doubling n doubles the number of iterations, which is what linear time means. The loop is also much faster than the recursive version, because every Fibonacci number is computed exactly once and then reused.

    Space: O(1). Only prev, curr, next and the loop counter exist, however large n is.

    Edge cases and common mistakes

    • Zero and one. fibonacci(0) is 0 and fibonacci(1) is 1. Without the early return, the loop would be skipped for these inputs and the function would wrongly return 1 for n = 0.
    • Overflow. F(46) is 1,836,311,903, the largest Fibonacci number that fits in an i32. F(47) would be 2,971,215,073, which doesn't fit. The lessons build Rust with optimizations, where integer overflow wraps silently, so fibonacci(47) returns -1323752223. A debug build would panic with an overflow error instead. Larger return types such as i64 or u64 push the limit further out.
    • Wrong update order. Writing curr = next; before prev = curr; makes prev and curr equal, and the sequence stops growing correctly.
    • Starting the loop at 1. With for i in 1..=n the loop runs one time too many and the result becomes F(n + 1). For n = 4 it would return 5 instead of 3.
    • Negative input. Since n < 2 catches every negative value, fibonacci(-3) returns -3. Fibonacci numbers aren't defined here for negative n, so no particular result is expected.

    Testing

    • n = 0 gives 0.
    • n = 1 gives 1.
    • n = 2 gives 1.
    • n = 3 gives 2.
    • n = 4 gives 3.
    • n = 10 gives 55.
    • n = 46 gives 1836311903.
    Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free