1137. N-th Tribonacci Number LeetCode Solution

In this guide, you will get 1137. N-th Tribonacci Number LeetCode Solution with the best time and space complexity. The solution to N-th Tribonacci Number problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
N-th Tribonacci Number solution in C++
N-th Tribonacci Number solution in Java
N-th Tribonacci Number solution in Python
Additional Resources

1137. N-th Tribonacci Number LeetCode Solution image

Problem Statement of N-th Tribonacci Number

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

Constraints:

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

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)

1137. N-th Tribonacci Number LeetCode Solution in C++

class Solution {
 public:
  int tribonacci(int n) {
    if (n < 2)
      return n;

    vector<int> dp{0, 1, 1};

    for (int i = 3; i <= n; ++i) {
      const int next = dp[0] + dp[1] + dp[2];
      dp[0] = dp[1];
      dp[1] = dp[2];
      dp[2] = next;
    }

    return dp[2];
  }
};
/* code provided by PROGIEZ */

1137. N-th Tribonacci Number LeetCode Solution in Java

class Solution {
  public int tribonacci(int n) {
    if (n < 2)
      return n;

    int[] dp = {0, 1, 1};

    for (int i = 3; i <= n; ++i) {
      final int next = dp[0] + dp[1] + dp[2];
      dp[0] = dp[1];
      dp[1] = dp[2];
      dp[2] = next;
    }

    return dp[2];
  }
}
// code provided by PROGIEZ

1137. N-th Tribonacci Number LeetCode Solution in Python

class Solution:
  def tribonacci(self, n: int) -> int:
    if n < 2:
      return n

    dp = [0, 1, 1]

    for _ in range(3, n + 1):
      dp[0], dp[1], dp[2] = dp[1], dp[2], sum(dp)

    return dp[2]
 # code by PROGIEZ