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).
This approach, also known as top-down dynamic programming, optimizes the brute-force recursion. It uses a data structure (like an array or map) to store the results of subproblems so that they don't need to be recomputed. This technique is called memoization.
Algorithm
- Create a memoization array
memoof sizen+1to store computed results. - Define a recursive helper function that takes
nandmemoas arguments. - In the helper, first check for base cases (n=0, 1, 2).
- Before computing, check if
memo[n]already holds a computed value. If so, return it. - If not, compute the result recursively:
trib(n-1) + trib(n-2) + trib(n-3). - Store the computed result in
memo[n]before returning it.
Walkthrough
We introduce a memo array to cache the results. The trib(n, memo) function first checks if the value for n has already been computed by looking it up in memo. If it exists, the cached value is returned immediately, avoiding redundant computation. If not, the value is computed recursively, stored in memo[n], and then returned. This ensures that each Tribonacci number from 0 to n is calculated only once.
class Solution { public int tribonacci(int n) { // Using an array of size 38 as per constraints 0 <= n <= 37 int[] memo = new int[38]; // Initialize with a value to indicate not computed, e.g., -1 // (or rely on default 0, but handle T_0=0 case) return trib(n, memo); } private int trib(int n, int[] memo) { if (n == 0) return 0; if (n == 1 || n == 2) return 1; if (memo[n] != 0) return memo[n]; memo[n] = trib(n - 1, memo) + trib(n - 2, memo) + trib(n - 3, memo); return memo[n]; }}Complexity
Time
O(n) - Each Tribonacci number from 0 to `n` is computed exactly once. The lookup and storage operations are constant time.
Space
O(n) - An array of size `n+1` is used for memoization, and the recursion stack can also go up to depth `n`.
Trade-offs
Pros
Drastically improves time complexity from exponential to linear.
Retains the logical structure of the recursive definition.
Cons
Uses O(n) space for the memoization array.
Incurs overhead from recursive function calls, which can be slightly less performant than an iterative solution.
This approach, also known as bottom-up dynamic programming, solves the problem iteratively. It builds a table of solutions for subproblems, starting from the smallest ones (the base cases) and working its way up to the target n.
Algorithm
- Handle the base cases for
n=0, 1, 2. - Create a
dparray of sizen+1. - Initialize the first three values:
dp[0] = 0,dp[1] = 1,dp[2] = 1. - Iterate from
i = 3ton. - In each iteration, calculate
dp[i]asdp[i-1] + dp[i-2] + dp[i-3]. - Return
dp[n]as the final result.
Walkthrough
Instead of using recursion, we use an array, dp, to store the Tribonacci numbers in order. We start by filling in the known base cases: dp[0], dp[1], and dp[2]. Then, we loop from 3 up to n, and for each index i, we calculate dp[i] by summing the three preceding values in the array (dp[i-1], dp[i-2], and dp[i-3]). This process fills the table from the bottom up. The final answer is the last value computed, dp[n].
class Solution { public int tribonacci(int n) { if (n == 0) return 0; if (n <= 2) return 1; int[] dp = new int[n + 1]; dp[0] = 0; dp[1] = 1; dp[2] = 1; for (int i = 3; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]; } return dp[n]; }}Complexity
Time
O(n) - We iterate through a single loop from 3 to `n`.
Space
O(n) - An array of size `n+1` is used to store the intermediate results.
Trade-offs
Pros
Efficient O(n) time complexity.
Avoids recursion overhead, which can make it slightly faster in practice than memoization.
Easy to understand and implement.
Cons
Requires O(n) space to store the entire table of Tribonacci numbers, which is not optimal.
This is the most efficient approach in terms of space. By observing the recurrence relation T_n = T_{n-1} + T_{n-2} + T_{n-3}, we can see that to compute any Tribonacci number, we only need the three previous ones. This allows us to discard older values and use only a constant amount of space.
Algorithm
- Handle base cases for
n=0, 1, 2. - Initialize three variables to hold the first three Tribonacci numbers:
t0 = 0,t1 = 1,t2 = 1. - Iterate from
i = 3ton. - In each iteration, calculate the next Tribonacci number:
nextVal = t0 + t1 + t2. - Update the three variables to 'slide' the window:
t0 = t1,t1 = t2,t2 = nextVal. - After the loop,
t2will hold the value forT_n. Returnt2.
Walkthrough
This method optimizes the tabulation approach by reducing the space complexity from O(n) to O(1). Instead of an entire array, we only use three variables to keep track of the last three computed Tribonacci numbers. Let's call them t0, t1, and t2, initialized to T_0, T_1, and T_2. We then loop from 3 to n. In each iteration, we calculate the next value as their sum. Then, we update the three variables to prepare for the next iteration: t0 takes the value of t1, t1 takes the value of t2, and t2 takes the newly computed value. This effectively slides our window of three numbers one step forward. The final result is the last computed value.
class Solution { public int tribonacci(int n) { if (n == 0) { return 0; } if (n == 1 || n == 2) { return 1; } int t0 = 0; int t1 = 1; int t2 = 1; for (int i = 3; i <= n; i++) { int nextVal = t0 + t1 + t2; t0 = t1; t1 = t2; t2 = nextVal; } return t2; }}Complexity
Time
O(n) - A single loop runs from 3 to `n`, performing constant time operations inside.
Space
O(1) - Only a constant number of variables are used, regardless of the input `n`.
Trade-offs
Pros
Optimal O(1) space complexity.
Efficient O(n) time complexity.
Simple and fast implementation, ideal for competitive programming and interviews.
Cons
For the given constraints, this approach has no significant cons and is considered optimal.
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; }}/** * @param {number} n * @return {number} */ var tribonacci = function (n) { let a = 0; let b = 1; let c = 1; while (n--) { let d = a + b + c; a = b; b = c; c = d; } return a;};class Solution {public: int tribonacci(int n) { long long a = 0, b = 1, c = 1; while (n--) { long long d = a + b + c; a = b; b = c; c = d; } return (int)a; }};class Solution: def tribonacci(self, n: int) -> int: a, b, c = 0, 1, 1 for _ in range(n): a, b, c = b, c, a + b + c return aVideo 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.