
Description
The Tribonacci sequence is similar to the Fibonacci sequence, but instead of starting with two initial numbers, it starts with three. Each number in the sequence is the sum of the three preceding ones. The sequence begins with 0, 1, 1, and continues as follows:
- T0 = 0
- T1 = 1
- T2 = 1
- T3 = T0 + T1 + T2
- T4 = T1 + T2 + T3
- and so forth.
Given an integer n
, the task is to compute the n-th Tribonacci number.
Intuition
To solve this problem, we need to keep track of the last three numbers in the Tribonacci sequence and compute the next number iteratively. By maintaining only the last three computed values, we can efficiently compute the result without using extra space.
Approach
- Base Cases:
- If
n
is 0, return 0. - Ifn
is 1 or 2, return 1, as these are the first few numbers in the Tribonacci sequence. - Iterative Computation:
- Initialize three variables
t0
,t1
, andt2
to 0, 1, and 1 respectively. - Iterate from 3 ton
, updating these variables to reflect the next number in the sequence. - For each iteration, compute the next number in the sequence ast0 + t1 + t2
, then shiftt0
,t1
, andt2
to the next positions. - Return:
- After completing the loop,
t2
will contain the n-th Tribonacci number.
Complexity
Time Complexity:
O(n), where n
is the input number. The function iterates from 3 to n
to compute the result.
Space Complexity:
O(1), as we only use a constant amount of space for the variables t0
, t1
, t2
, and t3
.
Code
C++
class Solution {
public:
int tribonacci(int n) {
if (n == 0) return 0;
if (n == 1 || n == 2) return 1;
int t0 = 0, t1 = 1, t2 = 1;
for (int i = 3; i <= n; ++i) {
int t3 = t0 + t1 + t2;
t0 = t1;
t1 = t2;
t2 = t3;
}
return t2;
}
};
Python
class Solution:
def tribonacci(self, n: int) -> int:
if n == 0:
return 0
if n == 1 or n == 2:
return 1
t0, t1, t2 = 0, 1, 1
for _ in range(3, n + 1):
t3 = t0 + t1 + t2
t0, t1, t2 = t1, t2, t3
return t2
Java
class Solution {
public int tribonacci(int n) {
if (n == 0) return 0;
if (n == 1 || n == 2) return 1;
int t0 = 0, t1 = 1, t2 = 1;
for (int i = 3; i <= n; i++) {
int t3 = t0 + t1 + t2;
t0 = t1;
t1 = t2;
t2 = t3;
}
return t2;
}
}
JavaScript
var tribonacci = function (n) {
if (n === 0) return 0;
if (n === 1 || n === 2) return 1;
let t0 = 0, t1 = 1, t2 = 1;
for (let i = 3; i <= n; i++) {
let t3 = t0 + t1 + t2;
t0 = t1;
t1 = t2;
t2 = t3;
}
return t2;
};