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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

N-th Tribonacci Number

Number: 1236

Difficulty: Easy

Paid? No

Companies: Google, Meta, tcs, Amazon, Adobe, Accenture, Coursera

Problem Description

Compute the n-th Tribonacci number where the sequence starts with T0 = 0, T1 = 1, T2 = 1, and for n >= 0, Tn+3 = Tn + Tn+1 + Tn+2.

Key Insights

  • The Tribonacci sequence is similar to Fibonacci but sums the last three numbers instead of two.
  • Base cases are provided for n = 0, 1, 2.
  • The problem can be solved iteratively using dynamic programming with constant space by updating three variables.
  • Given the constraints, an iterative solution is optimal.

Space and Time Complexity

Time Complexity: O(n) Space Complexity: O(1)

Solution

We use an iterative dynamic programming approach. For n less than or equal to 2, we directly return the base cases. For larger n, we maintain three variables corresponding to Tn-3, Tn-2, and Tn-1. In each iteration, we compute the current Tribonacci number as the sum of these three. We then update the variables accordingly, shifting them forward. This approach computes the result in O(n) time and uses O(1) space.

Code Solutions

# Function to compute the n-th Tribonacci number
def tribonacci(n):
    # Base cases: directly return when n is 0, 1, or 2
    if n == 0:
        return 0
    if n == 1 or n == 2:
        return 1

    # Initialize the first three Tribonacci numbers
    t0, t1, t2 = 0, 1, 1

    # Iteratively compute next Tribonacci numbers until we reach n
    for i in range(3, n + 1):
        current = t0 + t1 + t2  # current Tribonacci number
        # Update previous three values for next iteration
        t0, t1, t2 = t1, t2, current
    return t2

# Example usage
print(tribonacci(4))   # Expected output: 4
print(tribonacci(25))  # Expected output: 1389537
← Back to All Questions