N-th Tribonacci Number
EasyPrompt
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 = 4Example 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.
Approaches
4 approaches with complexity analysis and trade-offs.
This is the most straightforward approach, where the Tribonacci recurrence relation is directly translated into a recursive function. The function calls itself for the three preceding numbers until it reaches the base cases.
Algorithm
- Define a function
tribonacci(n). - If
nis 0, return 0. - If
nis 1 or 2, return 1. - Otherwise, return the sum of
tribonacci(n-1),tribonacci(n-2), andtribonacci(n-3).
Walkthrough
The function tribonacci(n) is defined to compute the n-th Tribonacci number. The base cases T_0 = 0, T_1 = 1, and T_2 = 1 are handled explicitly. For any n > 2, the function makes three recursive calls to compute tribonacci(n-1), tribonacci(n-2), and tribonacci(n-3), and returns their sum. This creates a recursion tree where many branches recalculate the same values. For instance, tribonacci(5) calculates tribonacci(4) and tribonacci(3). The call to tribonacci(4) will also calculate tribonacci(3), leading to redundant work.
class Solution { public int tribonacci(int n) { if (n == 0) { return 0; } if (n == 1 || n == 2) { return 1; } return tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3); }}Complexity
Time
O(3^n) - For each number `n`, the function makes three recursive calls. This leads to an exponential number of function calls, making it highly inefficient.
Space
O(n) - The space complexity is determined by the maximum depth of the recursion stack, which can go up to `n`.
Trade-offs
Pros
Very simple to understand and implement as it directly follows the mathematical definition.
Cons
Extremely inefficient due to re-computation of the same subproblems.
Will result in a 'Time Limit Exceeded' error for even moderately large values of
n(e.g., n > 30).
Solutions
Solution
class Solution {public int tribonacci(int n) { int a = 0, b = 1, c = 1; while (n-- > 0) { int d = a + b + c; a = b; b = c; c = d; } return a; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.