N-th Tribonacci Number

In this blog, we will learn Tribonacci Number and try to find out N-th Tribonacci Number.

Introduction

 

In this article, we will solve the leetcode problem #1137, N-th Tribonacci Number. Just like the N-th term of Fibonacci sequence is the sum of last two terms, the N-th term in Tribonnaci sequence is the sum of last three terms in the sequence. 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.

 

Constraints: 0 <= n <= 37. The answer is guaranteed to fit within a 32-bit integer, ie. answer <= 2^31 - 1.

static void Main(string[] args)
{
    var result = tribonacci(4);
    //result = 4
    result = tribonacci(25);
    //result = 1389537
}

Solution

 

The algorithm for solving the N-th Term of Tribonacci sequence is as follows,

1. Make an array F of length 38, and set F[0] = 0, F[1] = F[2] = 1.
2. Now write a loop where you set F[n+3] = F[n] + F[n+1] + F[n+2], and return F[n].

Here is the C# code for the approach,

static int tribonacci(int n)
{
    if (n <= 1)
    {
        return n;
    }
    int[] numbers = new int[n + 1];
    numbers[0] = 0;
    numbers[1] = 1;
    numbers[2] = 1;
    Enumerable.Range(3, n - 2).ToList().ForEach(i=> numbers[i] = numbers[i - 1] + numbers[i - 2] + numbers[i - 3]);
    return numbers[n];
}