1137. N-th Tribonacci Number

Problem Description

The Tribonacci sequence Tn is defined as follows:

T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.

Given n, return the value of Tn.

Solution 1: Dynamic Programming

This approach directly implements the recursive relation of the Tribonacci sequence using dynamic programming. We maintain three variables (a, b, c) to store the three most recently calculated Tribonacci numbers. In each iteration, we update these variables to calculate the next number in the sequence.

Time Complexity: O(n) - We iterate through the sequence up to n.

Space Complexity: O(1) - We use a constant amount of extra space to store the three variables.

Code:

Python:

class Solution:
    def tribonacci(self, n: int) -> int:
        a, b, c = 0, 1, 1
        for _ in range(n):
            a, b, c = b, c, a + b + c
        return a
 

Java:

class Solution {
    public int tribonacci(int n) {
        int a = 0, b = 1, c = 1;
        while (n-- > 0) {
            int d = a + b + c;
            a = b;
            b = c;
            c = d;
        }
        return a;
    }
}

C++:

class Solution {
public:
    int tribonacci(int n) {
        long long a = 0, b = 1, c = 1; // Use long long to avoid potential integer overflow
        while (n--) {
            long long d = a + b + c;
            a = b;
            b = c;
            c = d;
        }
        return (int) a;
    }
};

Other languages (Go, TypeScript, JavaScript, PHP) would follow similar logic.

Solution 2: Matrix Exponentiation

This approach uses matrix exponentiation to calculate the nth Tribonacci number in logarithmic time. The recurrence relation can be represented as a matrix multiplication:

[T(n+2), T(n+1), T(n)] = [T(n+1), T(n), T(n-1)] * [[1, 1, 1], [1, 0, 0], [0, 1, 0]] 

By repeatedly squaring the matrix, we can compute the nth power of the matrix efficiently in O(log n) time.

Time Complexity: O(log n) - Matrix exponentiation reduces the time complexity significantly.

Space Complexity: O(1) - Constant extra space is used.

Code: (Shown for Java, other languages are conceptually similar but might vary in matrix library usage)

class Solution {
    public int tribonacci(int n) {
        if (n == 0) return 0;
        if (n <= 2) return 1;
 
        int[][] base = {{1, 1, 1}, {1, 0, 0}, {0, 1, 0}};
        int[][] result = matrixPower(base, n - 2); //Start from [1,1,0]
 
        return result[0][0] + result[0][1] + result[0][2];
    }
 
    private int[][] matrixPower(int[][] base, int n) {
        int[][] res = {{1,0,0},{0,1,0},{0,0,1}}; // Identity matrix
        while(n > 0){
            if((n&1) == 1) res = matrixMultiply(res, base);
            base = matrixMultiply(base,base);
            n >>= 1;
        }
        return res;
    }
 
    private int[][] matrixMultiply(int[][] a, int[][] b){
        int[][] res = new int[3][3];
        for(int i=0; i<3; ++i){
            for(int j=0; j<3; ++j){
                for(int k=0; k<3; ++k){
                    res[i][j] += a[i][k] * b[k][j];
                }
            }
        }
        return res;
    }
}

The matrix multiplication and power functions are helper functions to handle the matrix operations efficiently. Note that the choice between these two solutions depends on the constraints of n. For smaller values of n, dynamic programming is simpler and might be faster. For larger n, matrix exponentiation offers a significant performance advantage.