Nth Tribonacci Number

Problem Link

N-th Tribonacci Number – LeetCode

Problem: N-th Tribonacci Number

Problem Statement

The Tribonacci sequence is defined as:

• T(0) = 0

• T(1) = 1

• T(2) = 1

• T(n) = T(n - 1) + T(n - 2) + T(n - 3) for n >= 3

Given n, return the value of T(n).

Examples

Example 1
Input: n = 4
Output: 4
Explanation: T(4) = T(3) + T(2) + T(1) = 2 + 1 + 1 = 4

Example 2
Input: n = 25
Output: 1389537

Constraints

• 0 <= n <= 37

• The answer will fit within a 32-bit integer.

Intuition

Tribonacci is an extension of the Fibonacci sequence with three previous terms instead of two.

To compute T(n), we recursively compute T(n-1), T(n-2), and T(n-3).

This is a classic recursive problem suitable for Induction – Base Case – Hypothesis explanation.

Induction – Base Case – Hypothesis Method

Function Signature

int tribonacci(int n)

Base Cases

• If n == 0, return 0

• If n == 1 || n == 2, return 1

These define the seed values of the Tribonacci sequence.

Hypothesis

Assume tribonacci(n-1), tribonacci(n-2), and tribonacci(n-3) return correct results.

Induction Step

Then tribonacci(n) can be computed as:

tribonacci(n) = tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3)

Approach

1. Handle the base cases directly.

2. Recursively call the function for the previous 3 terms.

3. Add them to get the current term.

Code (Java)

class Solution {
    public int tribonacci(int n) {
        // Base cases
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;

        // Hypothesis and Induction
        int first = tribonacci(n - 1);
        int second = tribonacci(n - 2);
        int third = tribonacci(n - 3);
        return first + second + third;
    }
}

Time and Space Complexity

• Time Complexity: O(3^n)

  • Each function call spawns three more calls → exponential growth.

• Space Complexity: O(n)

  • Due to recursion stack.

Note: This naive recursion is inefficient for large n. It can be optimized using memoization or dynamic programming.

Dry Run

Input: n = 4

tribonacci(4) 
= tribonacci(3) + tribonacci(2) + tribonacci(1)
= (tribonacci(2) + tribonacci(1) + tribonacci(0)) + 1 + 1
= (1 + 1 + 0) + 1 + 1 = 4

Conclusion

This problem reinforces the recursive mindset by extending Fibonacci into a 3-term recurrence. It's a good exercise in applying the Induction – Base – Hypothesis pattern. However, for performance, this method should eventually be replaced with memoization.