N-th Tribonacci Number Leetcode Solution

Difficulty Level Easy
Frequently asked in Facebook
algorithms coding Dynamic Programming Interview interviewprep LeetCode LeetCodeSolutionsViews 4294

Problem statement

In the problem ” N-th Tribonacci Number” we are given a number n. Our task is to find out the N-th tribonacci number.

The zeroth tribonacci number is 0. The first tribonacci number is 1. The second tribonacci number is 1.

N-th tribonacci number is summation of (N-1- th tribonacci number),  (N-2- th tribonacci number), and (N-3- th tribonacci number).

N-th Tribonacci Number Leetcode Solution

Example

n = 4
4

Explanation: As zeroth, first ,and second tribonacci numbers are 0,1,1 respectively. So the third tribonacci number is (0+1+1) 2. Likewise, the fourth tribonacci is (1+1+2) 4.

Approach for N-th Tribonacci Number Leetcode Solution

As N-th tribonacci number is defined as the summation of (N-1), (N-2), and (N-3) tribonacci number. So we first need the (N-3)-th tribonacci number this will be used in calculating (N-2), (N-1), and (N)-th tribonacci number. So now our new problem is to calculate (N-3)-th tribonacci number. Here we can conclude one thing that is to calculate the N-th tribonacci number we need to calculate one to N-th tribonacci number because every next value is dependent on the previous three values. We will follow these steps:

  1. We will store the values of zeroth, first and second tribonacci numbers in three variables namely a, b, and c respectively.
  2. Here a,b, and c will store the last three tribonacci numbers. Using these last three tribonacci numbers we will calculate the next tribonacci number and then update the values of a,b, and c.
  3. We will repeat step-2 until we find the value of the N-th tribonacci number then we will return it.

Implementation

C++ code for N-th Tribonacci Number

#include <bits/stdc++.h> 
using namespace std; 
    int tribonacci(int n) {
        if (n < 2) return n;
        int a = 0, b = 1, c = 1, d = a + b + c;
        while (n-- > 2) {
            d = a + b + c, a = b, b = c, c = d;
        }
        return c;
    }

int main() 
{ 
int n=4;
int ans=tribonacci(n); 
 cout<<ans<<endl;
 return 0;
}
4

Java code for N-th Tribonacci Number

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
import java.util.*; 
public class Tutorialcup {
    public static int tribonacci(int n) {
        if (n < 2) return n;
        int a = 0, b = 1, c = 1, d;
        while (n-- > 2) {
            d = a + b + c;
            a = b;
            b = c;
            c = d;
        }
        return c;
    }
  public static void main(String[] args) {
        int n=4; 
        int ans=tribonacci(n); 
        System.out.println(ans);
  }
}
4

Complexity Analysis of N-th Tribonacci Number Leetcode Solution

Time complexity

The time complexity of the above code is O(n) because we are iterating till the N-th tribonacci number. Here n is the given number for which we need to calculate N-th tribonacci number.

Space complexity

The space complexity of the above code is O(1) because we are using only a variable to store answer.

References

Translate »