N-th Tribonacci Number

N-th Tribonacci Number is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 1D Array (Fibonacci Style) subpattern.

Problem statement

The Tribonacci sequence is defined by three initial values: T0 = 0, T1 = 1, and T2 = 1. For every index k >= 3, the next value is the sum of the three preceding values: Tk = T(k - 1) + T(k - 2) + T(k - 3).

Given the integer parameter n, return Tn, the Tribonacci value at index n. The method must return the result as an integer.

Example 1:

Input: n = 2 Output: 1 Explanation: The second initial Tribonacci value is T2 = 1.

Example 2:

Input: n = 6 Output: 13 Explanation: Starting with 0, 1, 1, each later value sums the previous three, giving T6 = 13.

Example 3:

Input: n = 0 Output: 0 Explanation: The sequence is defined with T0 = 0.

Constraints:

- n is an integer. - 0 <= n <= 37. - The answer fits in a 32-bit signed integer.

Topics and companies

Topics: Dynamic Programming, Iteration, Math.

How to practise N-th Tribonacci Number on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.

Open N-th Tribonacci Number in the code editor, or read the N-th Tribonacci Number editorial for a worked solution with its approach and complexity analysis.

Where N-th Tribonacci Number sits in the DSA pattern sheet

Problems related to N-th Tribonacci Number

Other problems that use the same 1D Array (Fibonacci Style) and Dynamic Programming (DP) Patterns techniques:

Opening the problem

Progress is saved as you study.