1137. N-th Tribonacci Number
easyCompute the nth Tribonacci number where each term is the sum of the previous three. A natural extension of Fibonacci — same constant-space trick, one extra rolling variable.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Problem
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.
Constraints
0 <= n <= 37The answer is guaranteed to fit within a 32-bit integer, i.e., answer <= 2^31 - 1.
Examples
Example 1
n = 44Explanation: T_3 = 0 + 1 + 1 = 2, T_4 = 1 + 1 + 2 = 4.
Example 2
n = 251389537Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
Same shape as Fibonacci but with three base values and a three-term recurrence.
Hint 2
Memoize T(0)..T(n) into an array for O(n) time, O(n) space.
Hint 3
Three rolling variables (a, b, c) collapse the space to O(1).
Solution approach
Reveal approach
Bottom-up iteration with three rolling variables. Initialize a = 0, b = 1, c = 1 corresponding to T0, T1, T2. Loop i from 3 to n: compute next = a + b + c, then shift a = b, b = c, c = next. Return c after the loop. Handle n < 3 as base cases (return 0 for n=0, 1 for n=1 or n=2). The pattern is identical to Fibonacci — extra base case, extra rolling variable, same O(1) space.
Complexity
- Time
- O(n)
- Space
- O(1)
Related patterns
- dynamic-programming
- fibonacci
Related problems
- 509. Fibonacci Number
- 70. Climbing Stairs
- 746. Min Cost Climbing Stairs
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
Practice these live with InterviewChamp.AI
Drill N-th Tribonacci Number and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →