Dare2Solve
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:
Given an integer n
, the task is to compute the n-th Tribonacci number.
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.
Base Cases:
n
is 0, return 0.n
is 1 or 2, return 1, as these are the first few numbers in the Tribonacci sequence.Iterative Computation:
t0
, t1
, and t2
to 0, 1, and 1 respectively.n
, updating these variables to reflect the next number in the sequence.t0 + t1 + t2
, then shift t0
, t1
, and t2
to the next positions.Return:
t2
will contain the n-th Tribonacci number.O(n), where n
is the input number. The function iterates from 3 to n
to compute the result.
O(1), as we only use a constant amount of space for the variables t0
, t1
, t2
, and t3
.
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;
}
};
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
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;
}
}
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;
};