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
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.
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.