Skip to main content
CodePeetCodePeet
CodePeet 250

N-th Tribonacci Number

EASYProblemSolveExternal Links

Description

The Tribonacci sequence is defined as follows:

  • T(0) = 0
  • T(1) = 1
  • T(2) = 1
  • For n ≥ 3: T(n) = T(n-1) + T(n-2) + T(n-3)

This is a generalization of the Fibonacci sequence. Instead of summing the previous two numbers, each Tribonacci number is the sum of the previous three numbers.

Given an integer n, return the value of T(n).

Examples

Example 1

Input: n = 4

Output: 4

Explanation:

  • T(0) = 0
  • T(1) = 1
  • T(2) = 1
  • T(3) = T(2) + T(1) + T(0) = 1 + 1 + 0 = 2
  • T(4) = T(3) + T(2) + T(1) = 2 + 1 + 1 = 4

So T(4) = 4.

Example 2

Input: n = 25

Output: 1389537

Explanation: The Tribonacci sequence grows rapidly. By position 25, the value has reached 1,389,537. Computing this efficiently requires avoiding redundant calculations.

Example 3

Input: n = 0

Output: 0

Explanation: T(0) = 0 by definition. This is a base case — no computation is needed.

Constraints

  • 0 ≤ n ≤ 37
  • The answer is guaranteed to fit within a 32-bit integer, i.e., answer ≤ 2^31 - 1

Editorial

Brute Force

Intuition

The Tribonacci sequence has a natural recursive definition: each number is the sum of the three numbers before it. The most straightforward approach is to translate this definition directly into a recursive function.

Think of it like a family tree where each person needs to consult their three parents (yes, three!) to figure out their value. Person 0 knows they are 0, Person 1 knows they are 1, Person 2 knows they are 1. Everyone else asks their three predecessors and adds up the answers.

The recursive function tribonacci(n) returns T(0) = 0, T(1) = 1, or T(2) = 1 for the base cases. Otherwise, it recursively calls itself three times: tribonacci(n-1) + tribonacci(n-2) + tribonacci(n-3).

Step-by-Step Explanation

Let's trace through with n = 4.

Step 1: Call trib(4). Since 4 ≥ 3, we need trib(3) + trib(2) + trib(1).

Step 2: Recurse into trib(3). Since 3 ≥ 3, we need trib(2) + trib(1) + trib(0).

Step 3: Recurse into trib(2). Base case! Return 1.

Step 4: Recurse into trib(1). Base case! Return 1.

Step 5: Recurse into trib(0). Base case! Return 0.

Step 6: Compute trib(3) = trib(2) + trib(1) + trib(0) = 1 + 1 + 0 = 2.

Step 7: Back to trib(4): we now need trib(2). Recurse into trib(2) AGAIN — this is a duplicate call! Return 1.

Step 8: Back to trib(4): we need trib(1). Recurse into trib(1) AGAIN — another duplicate! Return 1.

Step 9: Compute trib(4) = trib(3) + trib(2) + trib(1) = 2 + 1 + 1 = 4.

Result: T(4) = 4.

Notice that trib(2) was computed twice and trib(1) was computed twice. For larger n, this redundancy grows exponentially — trib makes three recursive calls at each level, leading to O(3^n) total calls.

Brute Force Recursion — Exponential Branching — Watch how the recursion tree branches into three at each level, causing the same subproblems to be recomputed multiple times.

Algorithm

  1. Define a recursive function tribonacci(n).
  2. Base cases:
    • If n == 0, return 0.
    • If n == 1 or n == 2, return 1.
  3. Recursive case: return tribonacci(n-1) + tribonacci(n-2) + tribonacci(n-3).
  4. Call tribonacci(n) with the given input.

Code

class Solution {
public:
    int tribonacci(int n) {
        if (n == 0) return 0;
        if (n <= 2) return 1;
        return tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3);
    }
};
class Solution:
    def tribonacci(self, n: int) -> int:
        if n == 0:
            return 0
        if n <= 2:
            return 1
        return self.tribonacci(n - 1) + self.tribonacci(n - 2) + self.tribonacci(n - 3)
class Solution {
    public int tribonacci(int n) {
        if (n == 0) return 0;
        if (n <= 2) return 1;
        return tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3);
    }
}

Complexity Analysis

Time Complexity: O(3^n)

At each non-base call, the function makes three recursive calls. The recursion tree has a branching factor of 3, and the depth is n. Many subproblems overlap, but without memoization, each is recomputed every time it's encountered. The total number of calls is exponential — approximately O(3^n).

Space Complexity: O(n)

The maximum depth of the recursion stack is n (each call reduces n by at least 1). No additional data structures are used, so the space is dominated by the call stack: O(n).

Why This Approach Is Not Efficient

The brute force recursion has O(3^n) time complexity due to massive redundant computation. Each call spawns three more calls, and the same subproblems are solved over and over:

  • For n = 4: 7 total calls (2 redundant)
  • For n = 10: thousands of calls
  • For n = 37 (the constraint limit): approximately 3^37 ≈ 4.5 × 10^17 calls — completely infeasible

The problem is overlapping subproblems: trib(k) is needed by trib(k+1), trib(k+2), and trib(k+3). Without remembering past results, we recompute trib(k) from scratch each time.

The fix: store each computed value in a table (memoization) so every subproblem is solved exactly once. This converts the exponential tree into a linear chain.

Better Approach - Memoization (Top-Down DP)

Intuition

Memoization is like giving the recursive function a notebook. Before computing any value, it checks: "Have I solved this before?" If yes, it returns the stored answer instantly. If no, it computes the answer, writes it in the notebook, and then returns it.

The key insight is that there are only n+1 unique subproblems (trib(0) through trib(n)), but the brute force recursion visits them exponentially many times. By caching each result after the first computation, we ensure every subproblem is solved exactly once.

This transforms the exponential recursion tree into a linear sequence of unique computations: compute trib(0), trib(1), trib(2), ..., trib(n), each exactly once.

Step-by-Step Explanation

Let's trace with n = 4 and a memo table initialized with base cases: memo = [0, 1, 1, null, null].

Step 1: Initialize memo: memo[0]=0, memo[1]=1, memo[2]=1. Remaining entries are null.

Step 2: Call trib(4). memo[4] is null, so compute. Need trib(3), trib(2), trib(1).

Step 3: Call trib(3). memo[3] is null, so compute. Need trib(2), trib(1), trib(0).

Step 4: Look up trib(2) in memo → 1. Cache hit!

Step 5: Look up trib(1) in memo → 1. Cache hit!

Step 6: Look up trib(0) in memo → 0. Cache hit!

Step 7: Compute memo[3] = 1 + 1 + 0 = 2. Store in memo.

Step 8: Back to trib(4): look up trib(2) → 1 (cache hit!), trib(1) → 1 (cache hit!).

Step 9: Compute memo[4] = memo[3] + memo[2] + memo[1] = 2 + 1 + 1 = 4. Store in memo.

Step 10: Return memo[4] = 4.

Every subproblem was computed exactly once. The memo table did all the heavy lifting.

Memoization — Top-Down DP Table Filling — Watch how the memo table gets populated as recursive calls resolve. Cache hits eliminate all redundant computation.

Algorithm

  1. Create a memo dictionary or array.
  2. Set base cases: memo[0] = 0, memo[1] = 1, memo[2] = 1.
  3. Define recursive function trib(n):
    • If n is in memo, return memo[n] immediately.
    • Otherwise, compute memo[n] = trib(n-1) + trib(n-2) + trib(n-3).
    • Store result and return it.
  4. Call trib(n) with the given input.

Code

#include <vector>
using namespace std;

class Solution {
public:
    int tribonacci(int n) {
        if (n == 0) return 0;
        if (n <= 2) return 1;
        vector<int> memo(n + 1, -1);
        memo[0] = 0;
        memo[1] = 1;
        memo[2] = 1;
        return trib(n, memo);
    }

private:
    int trib(int n, vector<int>& memo) {
        if (memo[n] != -1) return memo[n];
        memo[n] = trib(n - 1, memo) + trib(n - 2, memo) + trib(n - 3, memo);
        return memo[n];
    }
};
class Solution:
    def tribonacci(self, n: int) -> int:
        memo = {0: 0, 1: 1, 2: 1}

        def trib(k: int) -> int:
            if k in memo:
                return memo[k]
            memo[k] = trib(k - 1) + trib(k - 2) + trib(k - 3)
            return memo[k]

        return trib(n)
import java.util.Arrays;

class Solution {
    public int tribonacci(int n) {
        if (n == 0) return 0;
        if (n <= 2) return 1;
        int[] memo = new int[n + 1];
        Arrays.fill(memo, -1);
        memo[0] = 0;
        memo[1] = 1;
        memo[2] = 1;
        return trib(n, memo);
    }

    private int trib(int n, int[] memo) {
        if (memo[n] != -1) return memo[n];
        memo[n] = trib(n - 1, memo) + trib(n - 2, memo) + trib(n - 3, memo);
        return memo[n];
    }
}

Complexity Analysis

Time Complexity: O(n)

Each subproblem trib(k) for k from 0 to n is computed exactly once and cached. There are n+1 subproblems, each requiring O(1) work (three lookups and one addition). Total: O(n).

Space Complexity: O(n)

The memo array stores n+1 values, requiring O(n) space. The recursion stack can also be up to O(n) deep. Total space: O(n).

Why This Approach Is Not Efficient

Memoization solves the time problem — O(n) instead of O(3^n). But it still uses O(n) space for two reasons:

  1. Memo array: Stores all n+1 computed values.
  2. Recursion stack: Up to n frames deep.

For n = 37 (the constraint limit), this is fine practically, but we can optimize further. The key observation: to compute T(n), we only need T(n-1), T(n-2), and T(n-3). Once we move past position k, we never need T(k-3) again.

This means we can replace the entire memo array with just three variables, computing bottom-up and sliding them forward. This eliminates both the array and the recursion overhead, achieving O(1) space.

Optimal Approach - Iterative with Constant Space

Intuition

Instead of recursing from the top and caching results, we flip the computation: start from the base cases and build upward, step by step. At each point, we only need the three most recent values.

Imagine a conveyor belt carrying three numbers. At each tick, we compute a new number from the three on the belt, push it on, and let the oldest one fall off. By the time the belt reaches position n, the newest number on it is our answer.

We use three variables — a, b, c — representing T(i-3), T(i-2), T(i-1) at each step. After computing T(i) = a + b + c, we shift: a becomes the old b, b becomes the old c, c becomes the new value. This sliding window of three values gives us O(1) space.

Step-by-Step Explanation

Let's trace with n = 4.

Step 1: Initialize three variables from the base cases: a = T(0) = 0, b = T(1) = 1, c = T(2) = 1.

Step 2: i = 3. Compute T(3) = a + b + c = 0 + 1 + 1 = 2.

Step 3: Shift the window: a ← b = 1, b ← c = 1, c ← T(3) = 2. Now a=1, b=1, c=2 represent T(1), T(2), T(3).

Step 4: i = 4. Compute T(4) = a + b + c = 1 + 1 + 2 = 4.

Step 5: Shift the window: a ← b = 1, b ← c = 2, c ← T(4) = 4. Now a=1, b=2, c=4 represent T(2), T(3), T(4).

Step 6: Loop ends (i has reached n). Return c = 4.

Only three variables used throughout — no array, no recursion. The answer slides naturally from the base cases to T(n).

Iterative Computation — Sliding Window of Three Variables — Watch three variables slide forward along the Tribonacci sequence, computing each new value from the three preceding ones using only O(1) space.

Algorithm

  1. Handle base cases: if n == 0, return 0. If n == 1 or n == 2, return 1.
  2. Initialize three variables: a = 0, b = 1, c = 1 (representing T(0), T(1), T(2)).
  3. Loop from i = 3 to n:
    • Compute next = a + b + c.
    • Shift the window: a = b, b = c, c = next.
  4. Return c.

Code

class Solution {
public:
    int tribonacci(int n) {
        if (n == 0) return 0;
        if (n <= 2) return 1;

        int a = 0, b = 1, c = 1;

        for (int i = 3; i <= n; i++) {
            int next = a + b + c;
            a = b;
            b = c;
            c = next;
        }

        return c;
    }
};
class Solution:
    def tribonacci(self, n: int) -> int:
        if n == 0:
            return 0
        if n <= 2:
            return 1

        a, b, c = 0, 1, 1

        for i in range(3, n + 1):
            a, b, c = b, c, a + b + c

        return c
class Solution {
    public int tribonacci(int n) {
        if (n == 0) return 0;
        if (n <= 2) return 1;

        int a = 0, b = 1, c = 1;

        for (int i = 3; i <= n; i++) {
            int next = a + b + c;
            a = b;
            b = c;
            c = next;
        }

        return c;
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate from 3 to n, performing one addition and three assignments per iteration. Each iteration is O(1), and there are n-2 iterations. Total: O(n).

Space Complexity: O(1)

We use only three integer variables (a, b, c) plus one temporary (next), regardless of input size. No arrays, no recursion stack. This is the optimal space usage — we need at least three previous values for the Tribonacci recurrence, and we achieve exactly that.