N-th Tribonacci Number

Problem Statement

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

Explanation

The problem involves computing the N-th Tribonacci number, where the Tribonacci sequence is defined as follows:

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

Detailed Steps:

1. Use three variables a, b, and c to keep track of the last three Tribonacci numbers (T(n-3), T(n-2), T(n-1)).
2. Base Cases:
   • If n == 0, return 0.
   • If n == 1 or n == 2, return 1.
3. Update the variables iteratively from 3 up to n using the recurrence relation:
   • next_trib = a + b + c
   • Update a, b, c accordingly for the next iteration.
4. After the loop, c will contain T(n), which is the N-th Tribonacci number.

Java Code

class Solution {
    public int tribonacci(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1 || n == 2) {
            return 1;
        }
        
        int a = 0, b = 1, c = 1;
        int nextTrib;
        
        for (int i = 3; i <= n; i++) {
            nextTrib = a + b + c;
            a = b;
            b = c;
            c = nextTrib;
        }
        
        return c;
    }
}

C++ Code

class Solution {
public:
    int tribonacci(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1 || n == 2) {
            return 1;
        }
        
        int a = 0, b = 1, c = 1;
        int nextTrib;
        
        for (int i = 3; i <= n; i++) {
            nextTrib = a + b + c;
            a = b;
            b = c;
            c = nextTrib;
        }
        
        return c;
    }
};

Python Code

class Solution:
    def tribonacci(self, n: int) -> int:
        if n == 0:
            return 0
        elif n == 1 or n == 2:
            return 1
        
        a, b, c = 0, 1, 1
        
        for i in range(3, n + 1):
            next_trib = a + b + c
            a = b
            b = c
            c = next_trib
        
        return c

Complexity Analysis

Time Complexity: O(N)
Space Complexity: O(1)