LESSON 167 OF 338 · LOOPS - CHALLENGES

Tribonacci Number in Go: O(n) Time and O(1) Space

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

Guided

Ctrl + Enter to check

GO · LOOPS - CHALLENGES

Tribonacci in Go, explained

Problem overview

The function tribonacci receives an integer n and returns T(n). This sequence is like Fibonacci, but each number is the sum of the three before it. It starts T(0) = 0, T(1) = 1 and T(2) = 1, and then T(n) = T(n - 1) + T(n - 2) + T(n - 3).

The sequence begins 0, 1, 1, 2, 4, 7, 13, 24. So T(3) = 1 + 1 + 0 = 2, T(4) = 2 + 1 + 1 = 4 and T(5) = 4 + 2 + 1 = 7. The task asks for O(n) time and O(1) extra space.

Approach: a window of three values

A direct recursion would call itself three times per level and repeat huge amounts of work. The loop version avoids that because each number depends only on the three before it. Keep those three in variables and move them forward one step per pass.

The variables are named by their distance from the newest value: curr is the newest, prev is one step behind it and prev2 two steps behind. At the start, they hold T(0), T(1) and T(2). Each pass computes the next number as their sum and shifts the window.

For n = 4: start with prev2 = 0, prev = 1, curr = 1. At i = 3 the sum is 2, and the window becomes (1, 1, 2). At i = 4 the sum is 4, and the window becomes (1, 2, 4). The answer is curr, which is 4.

Step by step

Base cases. If n is less than 2, return n, since T(0) = 0 and T(1) = 1.
Set the window. Declare prev2, prev and curr in one line with :=, as 0, 1 and 1: the values of T(0), T(1) and T(2). For n = 2 the loop below runs zero times and curr is already the answer.
Loop from 3 to n. Declare i starting at 3 and continue while i <= n. The <= includes n itself.
Compute the next number. Declare next as prev2 + prev + curr.
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 moved one place back.
Return curr, which holds T(n) after the last pass.

The solution in Go

func tribonacci(n int) int {
    if n < 2 {
        return n
    }
    prev2, prev, curr := 0, 1, 1
    for i := 3; i <= n; i++ {
        next := prev2 + prev + curr
        prev2 = prev
        prev = curr
        curr = next
    }
    return curr
}

Go details to notice:

Declaring several variables at once. prev2, prev, curr := 0, 1, 1 pairs names and values by position. The number of names must equal the number of values.
Shifting with a tuple assignment. Go evaluates the whole right side before assigning, so the three shifts could be written as prev2, prev, curr = prev, curr, next. The lesson uses three separate lines, which makes the order visible.
Order matters in separate lines. If you wrote prev = curr before prev2 = prev, prev2 would receive the already overwritten value and the window would collapse.
Everything is int. No conversions are needed. An int is 64 bits and wraps on overflow without any error. tribonacci(80) is 1500038259864032296 and still fits, while tribonacci(81) returns the negative number -3499197788614132815.

A longer trace

Here is the window after each pass for n = 6, starting from (0, 1, 1):

`i`	`prev2`	`prev`	`curr`
3	1	1	2
4	1	2	4
5	2	4	7
6	4	7	13

The function returns 13, so T(6) = 13. Each row's three values are the three numbers that produce the next row's curr: 2 + 1 + 1 = 4, then 4 + 2 + 1 = 7, then 7 + 4 + 2 = 13.

How it compares with Fibonacci

The structure is the same as in the Fibonacci problem, with a window of three instead of two. Two differences cause most slips. There are three base values, so the early return covers only 0 and 1 and the starting window is built to include T(2). And the loop starts at 3, not 2, because the window already holds everything up to T(2). The same pattern extends to any "sum of the previous k numbers" rule: keep k variables and shift them each pass, or use a slice of length k.

The same loop with one assignment

Because Go evaluates the whole right side before assigning anything, the three shifts and the sum can be a single statement. This loop body gives the same results as the lesson's version, including the table above:

for i := 3; i <= n; i++ {
    prev2, prev, curr = prev, curr, prev2+prev+curr
}

The lesson's version is easier to follow while you are learning, since each line does one thing. Use whichever you can read at a glance, but check it on a small input such as n = 4 after any rewrite.

Complexity

Time: O(n). The loop runs n - 2 times, with a few additions and assignments per pass.

Space: O(1). Four variables (prev2, prev, curr and next) plus the counter, regardless of n.

Edge cases and common mistakes

n = 0 and n = 1. Return n directly. Without that check, n = 0 would return 1, the starting value of curr.
n = 2. The loop doesn't run and the function returns 1, which is correct.
Starting the loop at 2. This would compute one extra number and return T(n + 1). The window already includes T(2), so the first number to compute is T(3).
Using i < n. This stops one step early and returns T(n - 1).
Mixing up Fibonacci's starting values. Tribonacci starts 0, 1, 1, not 0, 0, 1, so T(2) is 1.

Testing

n = 0 gives 0.
n = 2 gives 1.
n = 3 gives 2.
n = 5 gives 7.
n = 10 gives 149.

Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free