Tribonacci Series In Python

Problem Statement

Given a value N, your task is to print the Nth Tribonacci Number.

Examples:

Input: N = 4

Output: 2 

Input: N = 8

Output: 24

Explanation: The Nth Tribonacci number can be calculated by using the recursive formula, for N = 4 it will give 2, and for N = 8  it will give 24 as output.

Solution

There can be multiple approaches to solve this problem. At first, we will see the Brute Force solution, and then move on to the optimized solution. 

Method 1

The most naive way to solve this problem is to Solve using Recursion with the help of the given recurrence relation.

Let’s see the Code Implementation for Tribonacci Series in python.

# Tribonacci Series in python
# nth tribonacci number

def nthTribonacci(n):
    if(n==0 or n==1):
        return 0
    if(n==2):
        return 1
    
    return nthTribonacci(n-1)+nthTribonacci(n-2)+nthTribonacci(n-3)

n = 15
nthTribonacciNumber = nthTribonacci(n)
print(f'The {n}th Tribonacci Number is:',nthTribonacciNumber)

Output

The 15th Tribonacci Number is: 1705

Time Complexity: Exponential, approximately equal to O(N^3). As we are making three recursive calls.

Space Complexity: O(N), as auxiliary space complexity. A maximum of N elements can be present in the Recursive Stack Space at a time.

Method 2

A better solution to the problem would be to use Dynamic Programming.

TopDown DP - Memoization

We can memoize the recursive solution provided in Method 1. This will optimize the solution very much. 

Since there is a single changing variable in the Recursion, therefore we will create 1-D DP.

dp[n]. Initialize the DP with -1.

Let’s see the Code Implementation for Tribonacci Series in python.

# Tribonacci Series in python
# nth tribonacci number

def nthTribonacci(n):
    dp = [-1]*21
    dp[0] = dp[1] = 0
    dp[2] = 1
    def tribo(n):
        if(n==0 or n==1):
            return 0
        if(n==2):
            return 1
        if(dp[n]!=-1):
            return dp[n]
        nthNumber = nthTribonacci(n-1)+nthTribonacci(n-2)+nthTribonacci(n-3)
        dp[n] = nthNumber
        return nthNumber
    return tribo(n)

n = 20
nthTribonacciNumber = nthTribonacci(n)
print(f'The {n}th Tribonacci Number is:',nthTribonacciNumber)

Output

The 20th Tribonacci Number is: 35890

You can practice by yourself with the help of online python compiler for better understanding.
Time Complexity: O(N). Since we are storing the previous results into a list at max N recursive calls will happen.

Space Complexity: O(N), as we have declared a list of size N.

Also, O(N) is auxiliary space complexity. A maximum of N elements can be present in the Recursive Stack Space at a time.

Method 3

This method will help in reducing the Auxilary Space complexity used in Method 2.

Bottom Up DP - Tabulation

We will initialize our dp list with 0. dp[n]

Let’s see the Code Implementation for Tribonacci Series in python.

# Tribonacci Series in python
# nth tribonacci number

def nthTribonacci(n):
    dp = [0 for i in range(n + 1)]
    dp[0] = dp[1] = 0
    dp[2] = 1

    for i in range(3,n+1):
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
    return dp[n]

n = 18
nthTribonacciNumber = nthTribonacci(n)
print(f'The {n}th Tribonacci Number is:',nthTribonacciNumber)

Output

The 18th Tribonacci Number is: 10609

Time Complexity: O(N). Since we are running a for loop up to N times.

Space Complexity: O(N), as we have declared a list of size N.

Method 4

This method will solve this problem in O(1) Space Complexity.

Instead of taking a list of size N, we will take three variables to store the previous three results as our current result is completely dependent only on the previous three elements.

Space Optimization

Taking three variables, prev1=1, prev2=0, prev3=0.

Let’s see the Code Implementation for Tribonacci Series in python.

# Tribonacci Series in python
# nth tribonacci number

def nthTribonacci(n):
    prev3=0
    prev2=0
    prev1 = 1
    for i in range(3,n+1):
        curr = prev1+prev2+prev3
        prev3 = prev2
        prev2 = prev1
        prev1 = curr
    return prev1

n = 18
nthTribonacciNumber = nthTribonacci(n)
print(f'The {n}th Tribonacci Number is:',nthTribonacciNumber)

Output

The 18th Tribonacci Number is: 10609

Time Complexity: O(N), Since we are running a for loop up to N times.

Space Complexity: O(1), here we are taking any extra space instead we just have used three variables to store previous values.

Also check out - Rod Cutting Problem

You can also read about Palindrome Number in Python here.

Frequently Asked Questions

What is Fibonacci Series?

Fibonacci Series is a series of numbers in which each number (Fibonacci number) is the sum of the two preceding numbers. It is defined by the recurrence F(N) = F(N-1)+F(N-2).

What is Tribonacci Series?

Tribonacci series consists of numbers defined by the recurrence F(N) = F(N-1)+F(N-2)+F(N-3), which is similar to the Fibonacci sequence in which the previous two terms determine the following number; however, the Tribonacci series requires the preceding three terms.

What are the values of the first three Tribonacci Numbers?

The first three Tribonacci Number values are 0, 0, and 1, respectively.

What is a list in Python?

 Lists in Python is a data structure used to store multiple items in a single variable.

What is a String in Python?

A string in Python is a sequence of characters.

Conclusion

In this article, we have extensively discussed Tribonacci Series in Python and its recurrence relation, and also we have implemented it in Python using different Methods.

If you want to learn more, check out our articles on Flatten a Multi-level Linked List (Depth wise), Construct the Full K-ary Tree from its Preorder Traversal, Sum of all Unique Sub-array Sum for a Given Array, and Clone a Binary Tree with Random Pointers.

Do upvote our blog to help other ninjas grow.

Happy Coding!