N-th Tribonacci Number - Practice Coding Problems

N-th Tribonacci Number - Problem

The Tribonacci sequence T_n is defined as follows:

T₀ = 0
T₁ = 1
T₂ = 1
T_n+3 = T_n + T_n+1 + T_n+2 for n ≥ 0

Given n, return the value of T_n.

Note: This is a variation of the famous Fibonacci sequence where each term is the sum of the three preceding ones instead of two.

Input & Output

Example 1 — Small Value

$ Input: n = 4

› Output: 4

💡 Note: T(4) = T(1) + T(2) + T(3) = 1 + 1 + 2 = 4. The sequence is: T(0)=0, T(1)=1, T(2)=1, T(3)=2, T(4)=4.

Example 2 — Base Case

$ Input: n = 0

› Output: 0

💡 Note: T(0) = 0 by definition. This is one of the base cases.

Example 3 — Another Base Case

$ Input: n = 2

› Output: 1

💡 Note: T(2) = 1 by definition. Both T(1) and T(2) equal 1 as base cases.

Constraints

0 ≤ n ≤ 37
The answer is guaranteed to fit in a 32-bit integer

Visualization

Tap to expand

Understanding the Visualization

Base Cases

T(0)=0, T(1)=1, T(2)=1 are given

Pattern

Each T(n) = T(n-1) + T(n-2) + T(n-3)

Result

Build sequence up to T(n)

Key Takeaway

🎯 Key Insight: Each Tribonacci number is the sum of the three preceding numbers, making it perfect for dynamic programming optimization

Asked in

f Facebook 15 G Google 12 a Amazon 8

The key insight is that Tribonacci numbers follow a pattern where each term equals the sum of the three preceding terms. The optimal approach uses space-optimized dynamic programming with only 3 variables instead of storing all values. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Memoized Recursion	O(n)	O(n)	Cache results to avoid recalculating the same Tribonacci numbers
Recursive Brute Force	O(3ⁿ)	O(n)	Direct recursive implementation of the Tribonacci definition
Space-Optimized DP	O(n)	O(1)	Use only 3 variables instead of full array to track the last 3 values
Bottom-Up Dynamic Programming	O(n)	O(n)	Build up the solution iteratively from T(0) to T(n) using a DP array

Memoized Recursion — Algorithm Steps

Create a cache (dictionary/map) to store results
Check cache before making recursive calls
Store computed results in cache before returning

Visualization

Tap to expand

Step-by-Step Walkthrough

Cache Miss

First calculation stores result in cache

Cache Hit

Subsequent calls return cached value instantly

Efficiency

Each value computed only once

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

int cache[1000];
int initialized = 0;

int tribonacci(int n) {
    if (!initialized) {
        for (int i = 0; i < 1000; i++) cache[i] = -1;
        initialized = 1;
    }
    if (cache[n] != -1) return cache[n];
    if (n == 0) return cache[n] = 0;
    if (n == 1 || n == 2) return cache[n] = 1;
    return cache[n] = tribonacci(n-1) + tribonacci(n-2) + tribonacci(n-3);
}

int solution(int n) {
    return tribonacci(n);
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", solution(n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each value from 0 to n is calculated exactly once and cached

✓ Linear Growth

Space Complexity

O(n)

Cache stores n values plus recursion stack depth of n

⚡ Linearithmic Space

180.0K Views

Medium Frequency

~15 min Avg. Time

2.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Memoized Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler