Code Logo

N-th Tribonacci Number

Published at24 Jul 2026
Created by
Easy 1 views
Like0

The Tribonacci sequence is defined as:T0 = 0, T1 = 1, T2 = 1, and for n > 2, T(n) = T(n-1) + T(n-2) + T(n-3). Given n, return T(n). The Tribonacci sequence extends the Fibonacci concept by summing three previous terms instead of two.

This problem follows the same DP pattern as Fibonacci but with one additional state variable. The recurrence requires tracking three previous values instead of two, but the space-optimized approach still uses O(1) extra space by rolling the variables. The base cases are T0 = 0, T1 = 1, T2 = 1.

The bottom-up DP approach iterates from n = 3 to the target n, updating the three most recent values at each step. Time complexity is O(n), and space is O(1). Like Fibonacci, a naive recursive approach would have exponential time due to repeated subproblem computations.

Edge cases include n = 0 (return 0), n = 1 (return 1), and n = 2 (return 1). The sequence grows faster than Fibonacci and may exceed 32-bit integers for smaller n values.

The Tribonacci sequence grows faster than Fibonacci and has applications in combinatorics and counting problems where choices depend on three previous states. The rolling variable technique generalizes to any k-term recurrence with O(k) space and O(n) time.

Example Input & Output

Example 1
Input
6
Output
13
Explanation

T6 = T5+T4+T3 = 7+4+2 = 13.

Example 2
Input
0
Output
0
Explanation

T0 = 0.

Example 3
Input
4
Output
4
Explanation

T4 = T3+T2+T1 = 2+1+1 = 4.

Example 4
Input
5
Output
7
Explanation

T5 = T4+T3+T2 = 4+2+1 = 7.

Example 5
Input
1
Output
1
Explanation

T1 = 1.

Algorithm Flow

Recommendation Algorithm Flow for N-th Tribonacci Number

Solution Approach

Compute the n-th Tribonacci number where T0=0, T1=1, T2=1, and Tn = Tn-1 + Tn-2 + Tn-3 for n>2. Use dynamic programming with three rolling variables to avoid storing the full array. Initialize a=0, b=1, c=1 for T0, T1, T2. For n=0 or n=1 or n=2, return the appropriate base value directly.

function tribonacci(n) {
  if (n === 0) return 0;
  if (n <= 2) return 1;
  var a = 0, b = 1, c = 1;
  for (var i = 3; i <= n; i++) {
    var next = a + b + c;
    a = b; b = c; c = next;
  }
  return c;
}

The rolling window shifts forward: a gets the old b, b gets the old c, c gets the new sum. This uses O(1) space while computing the same values as the full DP array would.

Time complexity is O(n), space complexity is O(1).

Best Answers

java
class Solution {
    public int solution(int n) {
        if (n == 0) return 0;
        if (n <= 2) return 1;
        int a = 0, b = 1, c = 1;
        for (int i = 3; i <= n; i++) {
            int d = a + b + c;
            a = b;
            b = c;
            c = d;
        }
        return c;
    }
}