Compute a Three-Term Recurrence
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Other
### Problem
Define T0=0, T1=1, T2=1 and, for every i>=0, T(i+3)=Ti+T(i+1)+T(i+2). Return Tn for the supplied n.
```cpp
class Solution {
public:
int tribonacci(int n);
};
```
### Examples
**Example 1:**
```text
Input: n = 3
Output: 2
Explanation: T3=0+1+1=2.
```
**Example 2:**
```text
Input: n = 6
Output: 13
Explanation: T3=2,T4=4,T5=7, so T6=2+4+7=13.
```
### Constraints
- n is an integer in `[0,37]`.
- The answer fits a signed 32-bit integer.
### Contract considerations
Return the numeric value, without modular reduction.
```hint Read the boundary condition
What values are required at indices zero, one and two before the recurrence applies?
```
### Boundary reminders
Return the numeric value, without modular reduction.
Overview: Compute a Three-Term Recurrence. Define T0=0, T1=1, T2=1 and, for every i>=0, T(i+3)=Ti+T(i+1)+T(i+2).