1137. N-th Tribonacci Number

Description

The Tribonacci sequence T_n is defined as follows:

T₀ = 0, T₁ = 1, T₂ = 1, and T_n+3 = T_n + T_n+1 + T_n+2 for n >= 0.

Given n, return the value of T_n.

Example 1:

Input: n = 4
Output: 4
Explanation:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

Example 2:

Input: n = 25
Output: 1389537

Constraints:

0 <= n <= 37
The answer is guaranteed to fit within a 32-bit integer, ie. answer <= 2^31 - 1.

Solutions

Solution 1: Dynamic Programming

Thinking

Tribonacci is a three-term recurrence. With \(n\le 37\), a linear scan is enough. Three rolling variables hold the last terms; after \(n\) updates the first variable is \(T_n\), using constant extra space.

According to the recurrence relation given in the problem, we can use dynamic programming to solve it.

We define three variables \(a\), \(b\), \(c\) to represent \(T_{n-3}\), \(T_{n-2}\), \(T_{n-1}\), respectively, with initial values of \(0\), \(1\), \(1\).

Then we decrease \(n\) to \(0\), updating the values of \(a\), \(b\), \(c\) each time, until \(n\) is \(0\), at which point the answer is \(a\).

The time complexity is \(O(n)\), and the space complexity is \(O(1)\). Here, \(n\) is the given integer.

Python3JavaC++GoTypeScriptJavaScriptPHP

class Solution:
    def tribonacci(self, n: int) -> int:
        a, b, c = 0, 1, 1
        for _ in range(n):
            a, b, c = b, c, a + b + c
        return a

class Solution {
    public int tribonacci(int n) {
        int a = 0, b = 1, c = 1;
        while (n-- > 0) {
            int d = a + b + c;
            a = b;
            b = c;
            c = d;
        }
        return a;
    }
}

class Solution {
public:
    int tribonacci(int n) {
        long long a = 0, b = 1, c = 1;
        while (n--) {
            long long d = a + b + c;
            a = b;
            b = c;
            c = d;
        }
        return (int) a;
    }
};

func tribonacci(n int) int {
    a, b, c := 0, 1, 1
    for i := 0; i < n; i++ {
        a, b, c = b, c, a+b+c
    }
    return a
}

function tribonacci(n: number): number {
    let [a, b, c] = [0, 1, 1];
    while (n--) {
        let d = a + b + c;
        a = b;
        b = c;
        c = d;
    }
    return a;
}

/**
 * @param {number} n
 * @return {number}
 */
var tribonacci = function (n) {
    let a = 0;
    let b = 1;
    let c = 1;
    while (n--) {
        let d = a + b + c;
        a = b;
        b = c;
        c = d;
    }
    return a;
};

class Solution {
    /**
     * @param Integer $n
     * @return Integer
     */
    function tribonacci($n) {
        $a = 0;
        $b = 1;
        $c = 1;

        while ($n--) {
            $d = $a + $b + $c;
            $a = $b;
            $b = $c;
            $c = $d;
        }

        return $a;
    }
}

Solution 2: Matrix Exponentiation to Accelerate Recurrence

Thinking

Method 1 is \(O(n)\). Writing the recurrence as a \(1\times 3\) state times a \(3\times 3\) matrix lets binary exponentiation compute \(T_n\) with \(O(\log n)\) multiplications, which helps when \(n\) grows.

We define \(Tib(n)\) as a \(1 \times 3\) matrix \(\begin{bmatrix} T_n & T_{n - 1} & T_{n - 2} \end{bmatrix}\), where \(T_n\), \(T_{n - 1}\) and \(T_{n - 2}\) represent the \(n\)th, \((n - 1)\)th and \((n - 2)\)th Tribonacci numbers, respectively.

We hope to derive \(Tib(n)\) from \(Tib(n-1) = \begin{bmatrix} T_{n - 1} & T_{n - 2} & T_{n - 3} \end{bmatrix}\). That is, we need a matrix \(base\) such that \(Tib(n - 1) \times base = Tib(n)\), i.e.,

\[ \begin{bmatrix} T_{n - 1} & T_{n - 2} & T_{n - 3} \end{bmatrix} \times base = \begin{bmatrix} T_n & T_{n - 1} & T_{n - 2} \end{bmatrix} \]

Since \(T_n = T_{n - 1} + T_{n - 2} + T_{n - 3}\), the matrix \(base\) is:

\[ \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix} \]

We define the initial matrix \(res = \begin{bmatrix} 1 & 1 & 0 \end{bmatrix}\), then \(T_n\) is equal to the sum of all elements in the result matrix of \(res\) multiplied by \(base^{n - 3}\). This can be solved using matrix exponentiation.

The time complexity is \(O(\log n)\), and the space complexity is \(O(1)\).