N-TH TRIBONACCI NUMBER

By: Saurav

2019-08-18 00:38:00 UTC

Interview Question

The Tribonacci sequence : Leet Code

Question 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.


Example 1:

Input: n = 4
Output: 4
Explanation:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4
Example 2:

Input: n = 25
Output: 1389537

Solution

This question is just like nth Fibonacci but the equation will be:
f(n) = f(n-1) + f(n-2) + f(n-3)

But Leetcode wants us to solve this question through iteration, not recursion:

We have two edge cases already given and we know tribonacci(0), tribonacci(1) and tribonacci(2)

Algo:

Build an initial array arr -> [0,1,1]

If n is less than 3, return the corresponding element from the array arr[n]
 Otherwise, interactively fill up the array with new elements where the element at nth place is the sum of ( element at n-1st place + 
 element at n-2nd place + element at the n-3rd place )
 When the number of elements is n-1, stop iteration and return the last element

def tribonacci(n)
    arr = [0,1,1]
    return arr[n] if n < 3
    start = 3

    while start <= n
      arr << (arr[start-1]+arr[start-2]+arr[start-3])
      p arr
      start += 1
    end
    
    return arr[-1]
end

NoteWe could refactor it and separate the iteration part into another function but I feel this is a good balance. Refactoring and Single Responsibility Principle is great if it helps others read your code and understand it better. In this case, this function is easy enough to understand, therefore no need for abstractions.

When you print the array in each iteration, you can see how it builds up.
For n=5, the arrays changes like this:

[0, 1, 1, 2]
[0, 1, 1, 2, 4]
[0, 1, 1, 2, 4, 7]

For n=10, the array changes like:

[0, 1, 1, 2]
[0, 1, 1, 2, 4]
[0, 1, 1, 2, 4, 7]
[0, 1, 1, 2, 4, 7, 13]
[0, 1, 1, 2, 4, 7, 13, 24]
[0, 1, 1, 2, 4, 7, 13, 24, 44]
[0, 1, 1, 2, 4, 7, 13, 24, 44, 81]
[0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149]


Let me know what you think!
twitter: sprakash24oct
linkedin

Owned & Maintained by Saurav Prakash

If you like what you see, you can help me cover server costs or buy me a cup of coffee though donation :)