N-th Tribonacci Number

Easy
165.

N-th Tribonacci Number

EasyMathDynamic ProgrammingMemoizationAmazonGoogleAdobe

N-th Tribonacci Number is an easy coding problem on dynamic programming, math and memoization, asked in Amazon, Google and Adobe interviews.

The Tribonacci sequence T is defined by

T(0) = 0,  T(1) = 1,  T(2) = 1
T(n + 3) = T(n) + T(n + 1) + T(n + 2)   for n >= 0

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

Example 1

Input
n = 4
Output
4
Explanation
T(3) = 0 + 1 + 1 = 2, T(4) = 1 + 1 + 2 = 4.

Example 2

Input
n = 25
Output
1389537

Example 3

Input
n = 0
Output
0

Constraints

  • 0 <= n <= 37
  • The answer fits in a 32-bit integer.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var tribonacci = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in
AI InterviewGet started

N-th Tribonacci Number — Solution in Python, Java & C++

N-th Tribonacci Number solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

N-th Tribonacci Number is an easy coding problem on dynamic programming, math and memoization, asked in Amazon, Google and Adobe interviews.

Problem statement

The Tribonacci sequence T is defined by

T(0) = 0,  T(1) = 1,  T(2) = 1
T(n + 3) = T(n) + T(n + 1) + T(n + 2)   for n >= 0

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

Example 1

Input: n = 4
Output: 4
Explanation: T(3) = 0 + 1 + 1 = 2, T(4) = 1 + 1 + 2 = 4.

Example 2

Input: n = 25
Output: 1389537

Example 3

Input: n = 0
Output: 0

Constraints

  • 0 <= n <= 37
  • The answer fits in a 32-bit integer.

Hints for N-th Tribonacci Number

  1. Hint 1

    Same shape as Fibonacci, but the window is three values wide instead of two.

  2. Hint 2

    Seed a, b, c with T(0), T(1), T(2) and slide the window forward n - 2 times.

  3. Hint 3

    Handle n = 0, 1, 2 before the loop so the seeds are not overwritten.

How to solve N-th Tribonacci Number

Same as Fibonacci with a three-wide window: keep T(k), T(k+1), T(k+2) and slide.

Approach

  1. Return 0 for n == 0 and 1 for n == 1 or n == 2.
  2. Seed a, b, c = 0, 1, 1.
  3. For each k from 3 to n, set (a, b, c) = (b, c, a + b + c).
  4. Return c.

Why it works

The recurrence T(n+3) = T(n) + T(n+1) + T(n+2) depends on exactly the three previous terms, so a three-value window carries all the state a bottom-up computation needs.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Guard n < 3 before the loop, otherwise the seeds are read as if they were already advanced.
  • T(37) is the largest that fits in a 32-bit int.

Reference solution

Python

def tribonacci(n: int) -> int:
    if n == 0:
        return 0
    if n < 3:
        return 1
    a, b, c = 0, 1, 1
    for _ in range(3, n + 1):
        a, b, c = b, c, a + b + c
    return c

Java

public static int tribonacci(int n) {
    if (n == 0) return 0;
    if (n < 3) return 1;
    long a = 0, b = 1, c = 1;
    for (int i = 3; i <= n; i++) {
        long next = a + b + c;
        a = b;
        b = c;
        c = next;
    }
    return (int) c;
}

C++

int tribonacci(int n) {
    if (n == 0) return 0;
    if (n < 3) return 1;
    long long a = 0, b = 1, c = 1;
    for (int i = 3; i <= n; i++) {
        long long next = a + b + c;
        a = b;
        b = c;
        c = next;
    }
    return (int) c;
}

JavaScript

var tribonacci = function(n) {
    if (n === 0) return 0;
    if (n < 3) return 1;
    let a = 0, b = 1, c = 1;
    for (let i = 3; i <= n; i++) {
        const next = a + b + c;
        a = b;
        b = c;
        c = next;
    }
    return c;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 402 dynamic programming problems · the whole catalogue

Learn the technique: Dynamic Programming