Code Implementation

class Solution:
    def tribonacci(self, n: int) -> int:
        if n == 0:
            return 0
        if n == 1 or n == 2:
            return 1
        t0, t1, t2 = 0, 1, 1
        for i in range(3, n + 1):
            t_next = t0 + t1 + t2
            t0, t1, t2 = t1, t2, t_next
        return t2
      

class Solution {
public:
    int tribonacci(int n) {
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        int t0 = 0, t1 = 1, t2 = 1;
        for (int i = 3; i <= n; ++i) {
            int t_next = t0 + t1 + t2;
            t0 = t1;
            t1 = t2;
            t2 = t_next;
        }
        return t2;
    }
};
      

class Solution {
    public int tribonacci(int n) {
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        int t0 = 0, t1 = 1, t2 = 1;
        for (int i = 3; i <= n; i++) {
            int t_next = t0 + t1 + t2;
            t0 = t1;
            t1 = t2;
            t2 = t_next;
        }
        return t2;
    }
}
      

var tribonacci = function(n) {
    if (n === 0) return 0;
    if (n === 1 || n === 2) return 1;
    let t0 = 0, t1 = 1, t2 = 1;
    for (let i = 3; i <= n; i++) {
        let t_next = t0 + t1 + t2;
        t0 = t1;
        t1 = t2;
        t2 = t_next;
    }
    return t2;
};
      

Problem Description

The N-th Tribonacci Number problem asks you to compute the value of the n-th number in the Tribonacci sequence. The Tribonacci sequence is a generalization of the Fibonacci sequence where each term is the sum of the preceding three terms, with the following base cases:

• T0 = 0
• T1 = 1
• T2 = 1

For n >= 0, the sequence is defined as:
Tn = Tn-1 + Tn-2 + Tn-3 for n >= 3

Your task is to compute Tn for a given integer n (where 0 <= n <= 37).

Thought Process

The problem is similar to finding the Fibonacci sequence, but instead of summing the last two numbers, we sum the last three. A brute-force approach would be to use recursion, directly translating the definition into code. However, this leads to a lot of repeated calculations and is inefficient for larger n.

To optimize, we can use dynamic programming by storing previously computed results and building the sequence up from the base cases. This way, each number is computed only once, and we can avoid redundant calculations. Since we only need the last three computed values at any time, we can even optimize further by using three variables instead of an entire array.

Solution Approach

• First, handle the base cases: if n is 0, 1, or 2, return the corresponding value directly.
• For n >= 3:
  • Initialize three variables to represent T0, T1, and T2.
  • Iterate from 3 up to n, at each step computing the next Tribonacci number as the sum of the previous three.
  • Update the three variables to slide forward in the sequence.
• After the loop, the last updated variable holds the answer.

This approach is efficient because it only uses constant extra space and computes each Tribonacci number exactly once.

Example Walkthrough

Let's compute T4 step by step:

• Base cases: T0 = 0, T1 = 1, T2 = 1
• For n = 3:
  • T3 = T2 + T1 + T0 = 1 + 1 + 0 = 2
• For n = 4:
  • T4 = T3 + T2 + T1 = 2 + 1 + 1 = 4

So, the answer for n = 4 is 4.

Time and Space Complexity

• Brute-force (recursive): Each call makes three more calls, leading to exponential time complexity: O(3^n). Space complexity is O(n) due to the recursion stack.
• Optimized (iterative): We loop from 3 to n, so time complexity is O(n). Space complexity is O(1) because we only use three variables, regardless of n.

Summary

The N-th Tribonacci Number problem is a variation of the Fibonacci sequence that sums the last three numbers instead of two. While a naive recursive solution is straightforward, it is highly inefficient. By using an iterative dynamic programming approach and keeping track of only the last three values, we achieve a solution that is both fast and uses minimal memory. This makes the approach both elegant and practical for the problem constraints.