N-th Tribonacci Number

The key idea

Each Tribonacci term depends only on the previous three terms, so you never need the whole table — keep a rolling window of just three values and slide it forward n times. This drops the space from O(n) to O(1) while staying O(n) in time.

Problem

The Tribonacci sequence T_n is defined as follows: T_0 = 0, T_1 = 1, T_2 = 1, and T_(n+3) = T_n + T_(n+1) + T_(n+2) for every n >= 0.

Given an integer n, return the value of T_n.

Constraints

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

Examples

Input: n = 4 Output: 4

Input: n = 25 Output: 1389537

Complexity

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

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →