1137. N-th Tribonacci Number

Description

The Tribonacci sequence is similar to the Fibonacci sequence, but instead of starting with two initial numbers, it starts with three. Each number in the sequence is the sum of the three preceding ones. The sequence begins with 0, 1, 1, and continues as follows:

• T0 = 0
• T1 = 1
• T2 = 1
• T3 = T0 + T1 + T2
• T4 = T1 + T2 + T3
• and so forth.

Given an integer n, the task is to compute the n-th Tribonacci number.

Intuition

To solve this problem, we need to keep track of the last three numbers in the Tribonacci sequence and compute the next number iteratively. By maintaining only the last three computed values, we can efficiently compute the result without using extra space.

Approach

1. Base Cases: - If n is 0, return 0. - If n is 1 or 2, return 1, as these are the first few numbers in the Tribonacci sequence.
2. Iterative Computation: - Initialize three variables t0, t1, and t2 to 0, 1, and 1 respectively. - Iterate from 3 to n, updating these variables to reflect the next number in the sequence. - For each iteration, compute the next number in the sequence as t0 + t1 + t2, then shift t0, t1, and t2 to the next positions.
3. Return: - After completing the loop, t2 will contain the n-th Tribonacci number.

Complexity

Time Complexity:

O(n), where n is the input number. The function iterates from 3 to n to compute the result.

Space Complexity:

O(1), as we only use a constant amount of space for the variables t0, t1, t2, and t3.

Code

C++

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

Python

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):
            t3 = t0 + t1 + t2
            t0, t1, t2 = t1, t2, t3
        
        return t2

Java

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

JavaScript

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