algoadvance

The Tribonacci sequence Tn is defined as follows:

T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.

Given n, return the value of Tn.

Example 1:

Input: n = 4
Output: 4
Explanation:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

Example 2:

Input: n = 25
Output: 1389537

Clarifying Questions

1. Input Range:
   • What is the range of n?
     • The range of n is 0 <= n <= 37.
2. Constraints:
   • Is there any constraint on time complexity we need to meet?
     • Although not explicitly stated, the solution should be efficient to handle the upper bound.

Strategy

To solve this problem, we have a few approaches:

1. Recursive Approach:
   • Directly implement the recursive definition. However, this might be inefficient due to repeated calculations.
2. Memoization:
   • Use a dictionary or list to store previously computed values to avoid repeated calculations.
3. Dynamic Programming (Bottom-Up):
   • Iteratively compute values starting from base cases up to n. This approach is efficient and avoids the overhead of recursion.

Time Complexity

• Recursive Approach: Without memoization, the time complexity is exponential, specifically O(2^n), which is impractical for larger values of n.
• Memoization: Reduces the time complexity to O(n) with a space complexity of O(n).
• Dynamic Programming: Provides O(n) in both time and space complexity, which is the most optimal for this problem.

Given that n can go up to 37, we will use the dynamic programming approach for an efficient solution.

Code

def tribonacci(n: int) -> int:
    # Base cases
    if n == 0:
        return 0
    elif n == 1 or n == 2:
        return 1
    
    # Initialize the base values
    trib = [0] * (n + 1)
    trib[0] = 0
    trib[1] = 1
    trib[2] = 1
    
    # Fill the tribonacci series values up to nth
    for i in range(3, n + 1):
        trib[i] = trib[i - 1] + trib[i - 2] + trib[i - 3]
        
    return trib[n]

# Example usage:
print(tribonacci(4))  # Output: 4
print(tribonacci(25))  # Output: 1389537

Explanation

1. Base Cases:
   • We handle the simplest cases where n is 0, 1, or 2 directly by returning their known values.
2. Dynamic Programming Array Initialization:
   • Create an array trib where trib[i] holds the value of the i-th Tribonacci number.
3. Iterative Calculation:
   • Begin from index 3 and iteratively compute trib[i] using the formula trib[i] = trib[i - 1] + trib[i - 2] + trib[i - 3].
4. Return the Result:
   • Finally, return trib[n] as the result.

By following this approach, we ensure that we compute the Tribonacci number efficiently and within optimal time and space complexity.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?