Easy 0 solved 0% acceptance

Tribonacci

Return the nth tribonacci number, where each term is the sum of the three before it.

What you'll learn

  • Compute a sequence iteratively
  • Keep only the last few terms
  • Handle the starting terms directly

Problem

The tribonacci numbers extend the Fibonacci idea to three terms: T(0) = 0, T(1) = 0, T(2) = 1, and from then on T(n) = T(n − 1) + T(n − 2) + T(n − 3). The sequence goes 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, …

Implement tribonacci(n).

Input

n: The index of the term, starting at 0.

Output

Return T(n). Only the last three terms are needed at any time, so a loop with three variables is enough.

Constraints

0 ≤ n ≤ 74

Examples

Example 1
Input:
n = 7

Expected output:
expected = 13
Input:
long long n = 7;

Expected output:
long long expected = 13;
Input:
long n = 7;

Expected output:
long expected = 13;

Explanation

The terms are 0, 0, 1, 1, 2, 4, 7, 13, so T(7) = 13.

Example 2
Input:
n = 2

Expected output:
expected = 1
Input:
long long n = 2;

Expected output:
long long expected = 1;
Input:
long n = 2;

Expected output:
long expected = 1;

Explanation

T(2) is the first 1 in the sequence: 1.

How to approach it

Try on your own first, then open one hint at a time.

Hint 1

Return the first three terms directly.

Hint 2

Keep three variables and shift them along each step.

Hint 3

A recursive solution without memory repeats work and is far too slow.

Expected complexity

O(n) time, O(1) extra space

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

The best passing solution of each coder. Faster, smaller and better-reviewed solutions rank higher.

No passing solutions yet. Solve it to take first place.

Learn from others

Community solutions

No published solutions yet. Solve this challenge to share the first one.