Welcome to Subscribe On Youtube

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

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.

Solution 2: Matrix Exponentiation to Accelerate Recurrence

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)$.

• Java
• C++
• Python
• Go
• TypeScript
• Javascript
• Php

• 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;
      }
  };
  

• 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
  
  

• 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 {
      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;
  }
  
  

• /**
   * @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) {
          if ($n == 0) {
              return 0;
          } elseif ($n == 1 || $n == 2) {
              return 1;
          }
          $dp = [0, 1, 1];
          for ($i = 3; $i <= $n; $i++) {
              $dp[$i] = $dp[$i - 1] + $dp[$i - 2] + $dp[$i - 3];
          }
          return $dp[$n];
      }
  }
  
  

All Problems

All Solutions