Start learning free

LESSON 189 OF 414 · LOOPS - CHALLENGES

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

Practice Read the full explanation

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

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

Given n, calculate and return T(n).


Example 1:

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

Example 2:

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

Example 3:

Input: n = 5
Output: 7
Explanation: T(5) = T(4) + T(3) + T(2) = 4 + 2 + 1 = 7.

Note:

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


STEP 1 OF 8
    Ctrl + Enter to check

    RUST · LOOPS - CHALLENGES

    Tribonacci in Rust, explained

    Problem overview

    The function tribonacci takes an i32 called n and returns T(n). The sequence starts with T(0) = 0, T(1) = 1 and T(2) = 1, and from then on each number is the sum of the three before it: T(n) = T(n - 1) + T(n - 2) + T(n - 3).

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

    Approach: slide a window of three numbers

    Tribonacci is the Fibonacci idea with one more term. A direct recursive version would call itself three times per step and recompute the same values over and over, so it gets slow quickly. Building the sequence upward avoids that.

    To compute any term you need only the three terms just before it. So keep exactly three values, named by how far behind the newest value they are: curr is the newest, prev is one step behind and prev2 is two steps behind. Start them at T(0), T(1) and T(2), then repeat: add the three, shift each value one place back, and put the sum in the newest slot. After computing T(n), the newest slot holds the answer.

    Step by step

    1. Handle n < 2 first. T(0) = 0 and T(1) = 1 are their own answers, so return n when it is less than 2.
    2. Declare three i32 variables with let mut: prev2 = 0, prev = 1 and curr = 1. They hold T(0), T(1) and T(2). All three change inside the loop, so all three need mut.
    3. Loop over 3..=n. The terms still to compute are T(3) through T(n). The loop variable is named _ because the counter is never read. For n = 2 the range is empty, the loop runs zero times, and curr, which is already T(2), is returned as it is.
    4. Compute next as prev2 + prev + curr. It is created with a plain let, since each iteration makes a fresh one.
    5. Shift the window, oldest first. Assign prev to prev2, then curr to prev, then next to curr. Each variable is overwritten only after its old value has been copied one place back. Doing it in the opposite order would destroy values before they are used.
    6. Return curr as the last expression of the function, without a semicolon.

    Tracing n = 5: the window starts as (0, 1, 1). For T(3) the sum is 2 and the window becomes (1, 1, 2). For T(4) the sum is 4 and the window becomes (1, 2, 4). For T(5) the sum is 7 and the window becomes (2, 4, 7). The function returns 7.

    The solution in Rust

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

    Rust details worth knowing:

    • The last expression is the return value. curr has no semicolon, so it is the value of the function body. Adding a semicolon would turn it into a statement, the function would then return (), and the compiler would report a type mismatch. The early return n; inside the if does need the keyword, because it leaves the function from the middle.
    • The _ pattern. It accepts each value of the range and throws it away. It tells the reader, and the compiler, that the counter is intentionally unused, so there is no warning.
    • Inclusive ranges. 3..=n includes n. The half-open 3..n would stop one term early.
    • Type inference. next has no annotation. The compiler infers i32 from the three i32 values it adds.
    • Integers are copied. prev2 = prev copies an i32, so each assignment is independent and nothing is moved.

    Complexity

    Time: O(n). The loop runs n - 2 times for n of at least 3. Each pass does one three-way addition and three assignments.

    Space: O(1). The function keeps four integers (prev2, prev, curr and next), whatever n is.

    Edge cases and common mistakes

    • The three base values. tribonacci(0) is 0, tribonacci(1) is 1 and tribonacci(2) is 1. The first two come from the early return and the third from curr's starting value.
    • Starting the loop at 2. for _ in 2..=n adds one term too many, so tribonacci(2) would return 2 instead of 1.
    • Wrong shift order. Assigning curr = next before prev = curr makes prev and curr equal, and the sequence goes wrong from the next term on.
    • Overflow. T(37) is 2,082,876,103, the last term that fits in an i32. T(38) is 3,831,006,429, which doesn't. The lessons build Rust with optimizations, where integer overflow wraps silently, so tribonacci(38) returns -463960867. A debug build would panic with an overflow error instead. A wider type such as i64 or u64 moves the limit further out.
    • Allocating a vector. Storing the whole sequence in a Vec gives the right answers, but uses O(n) space instead of O(1).

    Testing

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