LESSON 167 OF 348 · LOOPS - CHALLENGES

Tribonacci Number in Kotlin: 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

KOTLIN · LOOPS - CHALLENGES

Tribonacci in Kotlin, explained

Problem overview

The function tribonacci(n: Int) returns T(n), the n-th Tribonacci number. The sequence starts with T(0) = 0, T(1) = 1 and T(2) = 1, and every later term is the sum of the three terms before it: T(n) = T(n - 1) + T(n - 2) + T(n - 3). The sequence begins 0, 1, 1, 2, 4, 7, 13, 24, 44.

For n = 4 the answer is 4, because T(4) = T(3) + T(2) + T(1) = 2 + 1 + 1. For n = 5 the answer is 7. The statement asks for O(n) time and O(1) space.

Approach

This is the Fibonacci idea with a window of three values instead of two. Each new term depends only on the three before it, so the algorithm never needs to remember earlier terms. Three variables hold the latest three terms. On each pass, add them to get the next term and slide the window forward by one place.

The variables are named by age. curr is the newest term, prev is the one before it, and prev2 is the one before that. They start at T(0), T(1) and T(2) (that is, prev2 = 0, prev = 1, curr = 1), so the first term the loop must compute is T(3).

Step by step

Base cases. If n < 2, return n, since T(0) = 0 and T(1) = 1.
Set up the window. Declare prev2 = 0, prev = 1 and curr = 1 with var, one per line. All three change later.
Loop from 3 to n. for (i in 3..n) computes T(3) up to T(n), one per pass. For n = 2 the range is empty, so the loop doesn't run and curr, which already holds T(2), is returned.
Compute the next term. val next = prev2 + prev + curr is T(i).
Shift the window, oldest first. prev2 = prev, then prev = curr, then curr = next. Each variable is overwritten only after its old value has been copied one place back.
Return curr. After the last pass it holds T(n).

Tracing n = 5: the window starts as 0, 1, 1. At i = 3, next = 2 and the window becomes 1, 1, 2. At i = 4, next = 4 and the window becomes 1, 2, 4. At i = 5, next = 7 and the window becomes 2, 4, 7. The function returns 7.

Why the loop is correct

At the start of the pass for i, prev2, prev and curr hold T(i - 3), T(i - 2) and T(i - 1). Before the first pass (i = 3) these are T(0), T(1) and T(2), which are the starting values. Each pass computes T(i) and shifts the window so the same statement holds for i + 1. When the loop is done, curr is T(n). This is also why the loop can start at 3 and why the case n = 2 needs no special code: the window already ends with T(2).

The solution in Kotlin

class Solution {
    fun tribonacci(n: Int): Int {
        if (n < 2) {
            return n
        }
        var prev2 = 0
        var prev = 1
        var curr = 1
        for (i in 3..n) {
            val next = prev2 + prev + curr
            prev2 = prev
            prev = curr
            curr = next
        }
        return curr
    }
}

Kotlin details:

Empty ranges are fine. 3..n with n less than 3 contains no numbers, so the loop body is skipped without an error. The call with n = 2 relies on this.
var and val. The window variables are reassigned, so they are var. next is created anew on each pass and never reassigned, so val is enough.
Int overflow. An Int wraps silently past 2147483647. tribonacci(37) returns 2082876103, the last value that fits. tribonacci(38) returns -463960867, which is wrong. Use Long when n can be larger.
Naming. next isn't a reserved word in Kotlin, so it is a valid variable name.

Complexity

Time: O(n). The loop runs n - 2 times with a constant amount of work in each pass.

Space: O(1). Four variables are enough, whatever n is. Storing the whole sequence in a list would take O(n) space, and a plain recursive definition would make an exponential number of calls.

From two variables to three

Compared with Fibonacci, only two things change: the window holds three values instead of two, and the loop starts at 3 instead of 2, because three starting values are known instead of two. The sliding pattern is the same, so you can extend it to any fixed number of previous terms. Each extra term adds one variable and one more assignment in the shifting block. The shifting always goes oldest first, so no value is overwritten before it is copied.

Because Int overflows early, a version with Long variables (0L, 1L, 1L) is worth knowing: it gives 3831006429 for T(38), where the Int version wraps to a negative number.

Edge cases and common mistakes

n = 0, 1 and 2. The first two return through the base case. For n = 2 the loop is skipped and curr is 1. Writing the base case as n < 3 with return n would be wrong, because it would give 2 for T(2), which is 1.
Wrong shift order. Setting curr = next before the other two assignments loses the old curr, and prev would take the new value instead of the old one.
Starting the loop at 2. That repeats the step for T(2), which is already known, and every result after it comes out too large.
Returning next. next only exists inside the loop, so this won't compile, and it would be missing when the loop is skipped. Use curr.
Overflow. Past n = 37, the result no longer fits an Int.

Testing

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

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

Start learning free