N-th Tribonacci Number

Problem Description

The Tribonacci sequence Tₙ is defined as follows:

• T₀ = 0, T₁ = 1, T₂ = 1, and Tₙ₊₃ = Tₙ + Tₙ₊₁ + Tₙ₊₂ for n ≥ 0.

Given n, return the value of Tₙ.

Examples

Constraints

• 0 ≤ n ≤ 37
• The answer is guaranteed to fit within a 32-bit integer, ie. Tₙ ≤ 2³¹ - 1.

Three-Variable State Tracking

To find the nth term, we only need the three preceding terms: Tₙ = Tₙ₋₁ + Tₙ₋₂ + Tₙ₋₃

Instead of keeping an array of size n + 1, we can use three variables t0, t1, and t2 initialized to 0, 1, and 1 respectively. On each step, we update them to transition to the next state: next = t0 + t1 + t2 t0 = t1 t1 = t2 t2 = next

Solution: O(1) Space DP

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 next = t0 + t1 + t2;
            t0 = t1;
            t1 = t2;
            t2 = next;
        }
        return t2;
    }
}

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 _ in range(3, n + 1):
            t0, t1, t2 = t1, t2, t0 + t1 + t2
        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 next = t0 + t1 + t2;
            t0 = t1;
            t1 = t2;
            t2 = next;
        }
        return t2;
    }
};

Complexity Analysis:

• Time Complexity: O(N) where N is the term index.
• Space Complexity: O(1) auxiliary space.

← All Problems