Tribonacci Number
Easy · Dynamic Programming · Math · Dynamic Programming · Memoization
Problem
The Tribonacci sequence starts with T0 = 0, T1 = 1 and T2 = 1. Every later term is the sum of the three terms before it:
T(n) = T(n - 1) + T(n - 2) + T(n - 3) for n >= 3.
Given a non-negative integer n, return Tn.
Examples
Input: n = 5 Output: 7
The sequence runs 0, 1, 1, 2, 4, 7, so T5 = 7.
Input: n = 0 Output: 0
T0 is one of the starting values.
Input: n = 10 Output: 149
Continuing: 13, 24, 44, 81, 149, so T10 = 149.
Constraints
- 0 <= n <= 37
- The answer fits in a signed 32-bit integer (T37 = 2,082,876,103).
Approaches
- Recursion with a memo — time O(n), space O(n)
Follow-up
For a huge n (say 10^18, answer taken modulo a prime), the three-term step is a fixed 3 x 3 matrix, and its n-th power by repeated squaring takes O(log n) multiplications. The use cases widen the window to k terms and push n to 10^18.
Related problems
Start free on Cariara · Coding problems · System design studio
