Solution: N-th Tribonacci Number

Statement#

Given a number n, calculate the corresponding Tribonacci number. The Tribonacci sequence $T_n$ is defined as:

The input number, n, is a non-negative integer.

Constraints:

• $0 \leq$ n $\leq 37$
• The answer is guaranteed to fit within a 32-bit integer, i.e., answer $\leq 2 ^{31} - 1$

Solution#

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which to follow based on considerations such as time complexity and implementation constraints.

Naive approach#

The first thing that comes to mind after reading the question is to use the same approach used for solving the Fibonacci sequence: recursion. The recursive approach works and will return us the correct answer here. We’ll first initialize three numbers as 0, 1, and 1. If our required Tribonacci number is 1 or 2, we’ll return 1 in the base case. Otherwise, we’ll call the function recursively three times to compute the next number’s sum, as the tribonacci number is the sum of the previous three numbers. We’ll repeat this process until we hit the base case.

Computing the nth tribonacci number this way takes $O(3^n)$ time and the space complexity of $O(n)$.

Optimized approach using dynamic programming#

We can reduce the time complexity if we use dynamic programming here. We can store the values of the elements and then reuse them to find the next element. When the specific element is needed, we just return the already stored value. This way, we don’t need the array of size n because at any given time we just need the value to be computed and the three values preceding it.

Here is how we’ll implement this algorithm:

• Initialize the first three variables as 0, 1, and 1.

• If n is less than 3, then return $1$.

• Otherwise, run a loop n-2 times and perform the following steps:

  • Replace the first variable with the second variable.

  • Replace the second variable with the third variable.

  • Replace the third variable with the sum of these three variables.

Solution summary#

To recap, the solution to this problem can be divided into the following parts:

• Initialize three variables as 0, 1, and 1, respectively.
• If $n$ is less than 3, then return 1.
• Otherwise, compute the next number by adding the last three numbers until the required number is obtained.

Time complexity#

The time complexity of this solution is $O(n)$, where n is the number of elements present in the array.

Space complexity#

The space complexity of this solution is $O(1)$, as we keep track of a constant number of variables at a time.