1137. N-th Tribonacci Number
Model: qwen2.5-coder:14b
Topics: Recursion
FAANG asked: 1
Acceptance rate: 56.1%
Problem Breakdown
The problem asks us to compute the N-th number in the Tribonacci sequence. The Tribonacci sequence is similar to the Fibonacci sequence but instead of each term being the sum of the two preceding ones, it is the sum of the three preceding terms. The sequence is defined as follows:
- T0 = 0
- T1 = 1
- T2 = 1
- For n >= 3, Tn = T(n-1) + T(n-2) + T(n-3)
Given an integer n, we need to return the value of Tn. The constraints are that 0 <= n <= 37, and the result is guaranteed to fit within a 32-bit integer.
Intuition
A brute-force approach would involve recursively calculating each term from scratch, which would lead to exponential time complexity due to repeated calculations of the same terms. This is inefficient for larger values of n.
The key insight is to use dynamic programming or memoization to store previously computed Tribonacci numbers and avoid redundant calculations. This will reduce the time complexity to linear.
Approach
We can use an iterative approach with a constant amount of space to compute the N-th Tribonacci number. We maintain three variables to store the last three terms of the sequence and update them iteratively until we reach the desired term.
- Initialize three variables:
a = 0,b = 1,c = 1representing T0, T1, and T2 respectively. - If
nis 0, returna. - If
nis 1 or 2, returnb. - For each number from 3 to
n, compute the next term as the sum of the previous three terms:next = a + b + c. - Update
a,b, andcto be the last three terms in the sequence. - Return
cafter the loop completes.
Complexity Analysis
- Time complexity: O(n) - We iterate from 3 to n, performing constant-time operations in each iteration.
- Space complexity: O(1) - We use a fixed amount of space regardless of the input size.
Solution
def tribonacci(n):
if n == 0:
return 0
elif n == 1 or n == 2:
return 1
a, b, c = 0, 1, 1
for i in range(3, n + 1):
next_term = a + b + c
a, b, c = b, c, next_term
return c
Edge Cases Handled
n = 0: The function returns 0 as expected.n = 1andn = 2: The function returns 1 for both cases, which are the base conditions.n = 37: The function computes the 37th Tribonacci number within the constraints provided.
The solution is correct, efficient, and clear. It handles all edge cases as specified in the problem statement.