We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

N-th Tribonacci Number

Difficulty: Easy

Problem Description

The Tribonacci sequence T_n is defined as follows: T_0 = 0, T_1 = 1, T_2 = 1, and T_n+3 = T_n + T_n+1 + T_n+2 for n >= 0. Given n, return the value of T_n.

Key Insights

  • The Tribonacci sequence is a generalization of the Fibonacci sequence, where each term is the sum of the three preceding terms.
  • The base cases are defined explicitly for T_0, T_1, and T_2.
  • For n > 2, the value can be calculated using previously computed values, making it suitable for dynamic programming approaches.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1) (if using a constant space approach)

Solution

To solve the problem, we can use an iterative approach to compute the Tribonacci numbers up to T_n. We'll maintain three variables to store the last three computed values, updating them in each step until we reach n. This approach is efficient and uses constant space, as we only need to keep track of the last three values.

Code Solutions

def tribonacci(n: int) -> int:
    if n == 0:
        return 0
    elif n == 1 or n == 2:
        return 1
    
    # Initialize the first three Tribonacci numbers
    t0, t1, t2 = 0, 1, 1
    for i in range(3, n + 1):
        # Calculate the next Tribonacci number
        t_next = t0 + t1 + t2
        # Update the last three values
        t0, t1, t2 = t1, t2, t_next
    
    return t2
← Back to All Questions