LeetCode 1137. N-th Tribonacci Number Solution in Java, C++, Python & More | Explanation + Code

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

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.

PythonJavaC++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(code-box)

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; } }(code-box)

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; } };(code-box)

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 }(code-box)

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; }(code-box)

/** * @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; };(code-box)

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; } }(code-box)

Solution 2: Matrix Exponentiation to Accelerate Recurrence

We define Tib(n) as a 1 × 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 nth, (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) × base = Tib(n), i.e.,

\begin{bmatrix} T_{n - 1} & T_{n - 2} & T_{n - 3} \end{bmatrix} × 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).

PythonJavaC++GoTypeScriptJavaScriptPHP

import numpy as np class Solution: def tribonacci(self, n: int) -> int: if n == 0: return 0 if n < 3: return 1 factor = np.asmatrix([(1, 1, 0), (1, 0, 1), (1, 0, 0)], np.dtype("O")) res = np.asmatrix([(1, 1, 0)], np.dtype("O")) n -= 3 while n: if n & 1: res *= factor factor *= factor n >>= 1 return res.sum()(code-box)

class Solution { public int tribonacci(int n) { if (n == 0) { return 0; } if (n < 3) { return 1; } int[][] a = {{1, 1, 0}, {1, 0, 1}, {1, 0, 0}}; int[][] res = pow(a, n - 3); int ans = 0; for (int x : res[0]) { ans += x; } return ans; } private int[][] mul(int[][] a, int[][] b) { int m = a.length, n = b[0].length; int[][] c = new int[m][n]; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { for (int k = 0; k < b.length; ++k) { c[i][j] += a[i][k] * b[k][j]; } } } return c; } private int[][] pow(int[][] a, int n) { int[][] res = {{1, 1, 0}}; while (n > 0) { if ((n & 1) == 1) { res = mul(res, a); } a = mul(a, a); n >>= 1; } return res; } }(code-box)

class Solution { public: int tribonacci(int n) { if (n == 0) { return 0; } if (n < 3) { return 1; } vector<vector<ll>> a = {{1, 1, 0}, {1, 0, 1}, {1, 0, 0}}; vector<vector<ll>> res = pow(a, n - 3); return accumulate(res[0].begin(), res[0].end(), 0); } private: using ll = long long; vector<vector<ll>> mul(vector<vector<ll>>& a, vector<vector<ll>>& b) { int m = a.size(), n = b[0].size(); vector<vector<ll>> c(m, vector<ll>(n)); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { for (int k = 0; k < b.size(); ++k) { c[i][j] += a[i][k] * b[k][j]; } } } return c; } vector<vector<ll>> pow(vector<vector<ll>>& a, int n) { vector<vector<ll>> res = {{1, 1, 0}}; while (n) { if (n & 1) { res = mul(res, a); } a = mul(a, a); n >>= 1; } return res; } };(code-box)

func tribonacci(n int) (ans int) { if n == 0 { return 0 } if n < 3 { return 1 } a := [][]int{{1, 1, 0}, {1, 0, 1}, {1, 0, 0}} res := pow(a, n-3) for _, x := range res[0] { ans += x } return } func mul(a, b [][]int) [][]int { m, n := len(a), len(b[0]) c := make([][]int, m) for i := range c { c[i] = make([]int, n) } for i := 0; i < m; i++ { for j := 0; j < n; j++ { for k := 0; k < len(b); k++ { c[i][j] += a[i][k] * b[k][j] } } } return c } func pow(a [][]int, n int) [][]int { res := [][]int{{1, 1, 0}} for n > 0 { if n&1 == 1 { res = mul(res, a) } a = mul(a, a) n >>= 1 } return res }(code-box)

function tribonacci(n: number): number { if (n === 0) { return 0; } if (n < 3) { return 1; } const a = [ [1, 1, 0], [1, 0, 1], [1, 0, 0], ]; return pow(a, n - 3)[0].reduce((a, b) => a + b); } function mul(a: number[][], b: number[][]): number[][] { const [m, n] = [a.length, b[0].length]; const c = Array.from({ length: m }, () => Array.from({ length: n }, () => 0)); for (let i = 0; i < m; ++i) { for (let j = 0; j < n; ++j) { for (let k = 0; k < b.length; ++k) { c[i][j] += a[i][k] * b[k][j]; } } } return c; } function pow(a: number[][], n: number): number[][] { let res = [[1, 1, 0]]; while (n) { if (n & 1) { res = mul(res, a); } a = mul(a, a); n >>= 1; } return res; }(code-box)

/** * @param {number} n * @return {number} */ var tribonacci = function (n) { if (n === 0) { return 0; } if (n < 3) { return 1; } const a = [ [1, 1, 0], [1, 0, 1], [1, 0, 0], ]; return pow(a, n - 3)[0].reduce((a, b) => a + b); }; function mul(a, b) { const [m, n] = [a.length, b[0].length]; const c = Array.from({ length: m }, () => Array.from({ length: n }, () => 0)); for (let i = 0; i < m; ++i) { for (let j = 0; j < n; ++j) { for (let k = 0; k < b.length; ++k) { c[i][j] += a[i][k] * b[k][j]; } } } return c; } function pow(a, n) { let res = [[1, 1, 0]]; while (n) { if (n & 1) { res = mul(res, a); } a = mul(a, a); n >>= 1; } return res; }(code-box)

class Solution { /** * @param Integer $n * @return Integer */ function tribonacci($n) { if ($n === 0) { return 0; } if ($n < 3) { return 1; } $a = [[1, 1, 0], [1, 0, 1], [1, 0, 0]]; $res = $this->pow($a, $n - 3); return array_sum($res[0]); } private function mul($a, $b) { $m = count($a); $n = count($b[0]); $p = count($b); $c = array_fill(0, $m, array_fill(0, $n, 0)); for ($i = 0; $i < $m; ++$i) { for ($j = 0; $j < $n; ++$j) { for ($k = 0; $k < $p; ++$k) { $c[$i][$j] += $a[$i][$k] * $b[$k][$j]; } } } return $c; } private function pow($a, $n) { $res = [[1, 1, 0]]; while ($n > 0) { if ($n & 1) { $res = $this->mul($res, $a); } $a = $this->mul($a, $a); $n >>= 1; } return $res; } }(code-box)