N Th Tribonacci Number - Leetcode Solution

Problem statement: 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: In this problem, we need to find the nth Tribonacci number. We can solve this problem in multiple ways, but the easiest solution is to use the memoization technique.

In the memoization technique, we store the values of the previous numbers and use them to calculate the next number. To implement this solution, we create an array that stores the values of the previous three Tribonacci numbers. We initialize the array with the initial values of the sequence (0, 1, 1). Then we use a loop that starts from 3 and iterates up to n. In each iteration, we calculate the next Tribonacci number by summing up the previous three numbers and store it in the array.

After the loop ends, the nth Tribonacci number is stored in the last element of the array. We return this element as the answer.

Here is the Python code for the solution:

class Solution: def tribonacci(self, n: int) -> int: if n == 0: return 0 if n == 1 or n == 2: return 1 t = [0] * (n + 1) t[0] = 0 t[1] = 1 t[2] = 1 for i in range(3, n + 1): t[i] = t[i - 1] + t[i - 2] + t[i - 3] return t[n]

In this code, we check if the input value of n is 0, 1, or 2. If it is any of those, we return the relevant initial value of the sequence. Otherwise, we create an array of size n+1 and initialize it with the initial values of the sequence. We then use a loop to calculate the next Tribonacci numbers and store them in the array. Finally, we return the nth element of the array as the answer.

Time Complexity Analysis: The time complexity of the above solution is O(n), as we need to calculate n elements of the sequence and store them in an array. But as we are using memoization, we are not calculating the same Tribonacci numbers multiple times. So, the time complexity of this method is optimal.

Space Complexity Analysis: The space complexity of the above solution is O(n), as we need to store the values of n+1 Tribonacci numbers in the array.

1