Jobs

Interviews

Discussions

N-th Tribonacci Number

Easy

Coursera

9 views

Topics:

ArraysDynamic Programming

The Tribonacci sequence T_n is defined as follows:

T₀ = 0, T₁ = 1, T₂ = 1, and T_n+3 = T_n + T_n+1 + T_n+2 for n >= 0.

Given n, return the value of T_n.

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

Constraints:

0 <= n <= 37
The answer is guaranteed to fit within a 32-bit integer, ie. answer <= 2^31 - 1.

Try coding it in LeetCode

N-th Tribonacci Number

Easy

Coursera

9 views

Topics:

ArraysDynamic Programming

The Tribonacci sequence T_n is defined as follows:

T₀ = 0, T₁ = 1, T₂ = 1, and T_n+3 = T_n + T_n+1 + T_n+2 for n >= 0.

Given n, return the value of T_n.

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

Constraints:

0 <= n <= 37
The answer is guaranteed to fit within a 32-bit integer, ie. answer <= 2^31 - 1.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected range for the input integer n? Are there any upper or lower bounds?
Should I assume n will always be a non-negative integer?
For very small values of n (e.g., 0, 1, 2), can I simply return the corresponding Tribonacci number directly, or is there a specific optimization I should consider for these base cases?
Is the primary focus of the solution to be clarity and correctness, or should I prioritize code optimization for performance given the potential range of n?
Should I use iterative dynamic programming, recursion with memoization, or any other specific approach?

Brute Force Solution

Approach

To find the N-th Tribonacci number, we can directly apply the definition. The core idea is to repeatedly calculate each number in the sequence until we reach the one we are looking for, without storing intermediate values in a table or using memoization.

Here's how the algorithm would work step-by-step:

Recognize that the first three Tribonacci numbers are pre-defined: the 0th is 0, the 1st is 1, and the 2nd is 1.
If we are looking for any of these first three numbers, we simply return the pre-defined value.
If we are looking for any subsequent number, we compute it by summing the previous three Tribonacci numbers.
To compute the next number, we repeat the process of summing the three immediately preceding values. We keep doing this until we've calculated up to the N-th number.
Once we reach the N-th Tribonacci number, we can simply return it as our final answer.

Code Implementation

def tribonacci_brute_force(n):
    # Define the base cases as specified
    if n == 0:
        return 0

    if n == 1:
        return 1

    if n == 2:
        return 1

    tribonacci_zero = 0
    tribonacci_one = 1
    tribonacci_two = 1

    # Iterate up to n to find the nth Tribonacci number
    for i in range(3, n + 1):
        tribonacci_current = tribonacci_zero + tribonacci_one + tribonacci_two

        # Shift the variables to calculate the next Tribonacci number
        tribonacci_zero = tribonacci_one
        tribonacci_one = tribonacci_two
        tribonacci_two = tribonacci_current

    return tribonacci_two

Big(O) Analysis

Time Complexity

O(n) – The algorithm iteratively calculates the Tribonacci numbers from the 3rd number up to the N-th number. For each number, it performs a constant number of operations which is summing the previous three numbers. Since this process repeats 'n' times in the worst case, where 'n' is the input, the time complexity is directly proportional to n.

Space Complexity

O(1) – The algorithm uses only a fixed number of variables to store the three most recent Tribonacci numbers during the iterative calculation, regardless of the value of N. There are no auxiliary data structures like arrays, lists, or recursion stacks used. Therefore, the auxiliary space used is constant and does not depend on the input N. This constant space usage leads to a space complexity of O(1).

Optimal Solution

Approach

The goal is to quickly find a specific number in a sequence where each number is the sum of the previous three. Instead of recalculating the same sums over and over, we can remember previous calculations to find the answer much faster.

Here's how the algorithm would work step-by-step:

Recognize that finding a number in this sequence relies on knowing the three numbers before it.
Start with the first three numbers of the sequence, which are already known.
To find the next number, simply add the three previous numbers that you already have.
Store this new number, so that you can use it in later calculations.
Repeat the adding and storing process until you reach the number you're looking for.
By keeping track of the numbers we've already calculated, we avoid repeating work and find the answer efficiently.

Code Implementation

def tribonacci(n):
    if n == 0:
        return 0
    if n == 1 or n == 2:
        return 1

    # Initialize the first three Tribonacci numbers.
    tribonacci_numbers = [0, 1, 1]

    # Iterate to calculate Tribonacci numbers up to n.
    for i in range(3, n + 1):
        # Calculate the next Tribonacci number.
        next_tribonacci_number = tribonacci_numbers[0] + tribonacci_numbers[1] + tribonacci_numbers[2]

        # Update the list to store the latest three numbers.
        tribonacci_numbers[0] = tribonacci_numbers[1]
        tribonacci_numbers[1] = tribonacci_numbers[2]
        tribonacci_numbers[2] = next_tribonacci_number

    # The last element is the nth Tribonacci number
    return tribonacci_numbers[2]

Big(O) Analysis

Time Complexity

O(n) – The provided solution iteratively calculates the Tribonacci numbers up to the nth number. It starts with the base cases and then proceeds to calculate subsequent values by summing the three previous ones. This process continues until the nth Tribonacci number is reached. The number of iterations is directly proportional to n, meaning the time complexity grows linearly with the input size n.

Space Complexity

O(1) – The algorithm described stores only the three most recent Tribonacci numbers to calculate the next one. Regardless of the value of N, we only need space for these three numbers. Therefore, the auxiliary space required remains constant irrespective of the input size N, leading to a space complexity of O(1).

Edge Cases

Case	How to Handle
n is 0	Return 0 as defined by T0 = 0.
n is 1	Return 1 as defined by T1 = 1.
n is 2	Return 1 as defined by T2 = 1.
n is a large positive integer	Use dynamic programming (iterative approach) to avoid recursion depth issues and optimize for time complexity.
Integer overflow for large n	Consider using a larger data type (e.g., long) or modulo operation if the problem specifies a modulo.
n is negative	Return an error or define the Tribonacci sequence for negative indices (uncommon, needs clarification).
n is a very large number that would exceed memory capacity when using DP array	Optimize space complexity by using only three variables to store the last three Tribonacci numbers.
Input is not an integer	Validate input type to ensure it is an integer.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected range for the input integer n? Are there any upper or lower bounds?
Should I assume n will always be a non-negative integer?
For very small values of n (e.g., 0, 1, 2), can I simply return the corresponding Tribonacci number directly, or is there a specific optimization I should consider for these base cases?
Is the primary focus of the solution to be clarity and correctness, or should I prioritize code optimization for performance given the potential range of n?
Should I use iterative dynamic programming, recursion with memoization, or any other specific approach?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Recognize that the first three Tribonacci numbers are pre-defined: the 0th is 0, the 1st is 1, and the 2nd is 1.
If we are looking for any of these first three numbers, we simply return the pre-defined value.
If we are looking for any subsequent number, we compute it by summing the previous three Tribonacci numbers.
To compute the next number, we repeat the process of summing the three immediately preceding values. We keep doing this until we've calculated up to the N-th number.
Once we reach the N-th Tribonacci number, we can simply return it as our final answer.

Code Implementation

def tribonacci_brute_force(n):
    # Define the base cases as specified
    if n == 0:
        return 0

    if n == 1:
        return 1

    if n == 2:
        return 1

    tribonacci_zero = 0
    tribonacci_one = 1
    tribonacci_two = 1

    # Iterate up to n to find the nth Tribonacci number
    for i in range(3, n + 1):
        tribonacci_current = tribonacci_zero + tribonacci_one + tribonacci_two

        # Shift the variables to calculate the next Tribonacci number
        tribonacci_zero = tribonacci_one
        tribonacci_one = tribonacci_two
        tribonacci_two = tribonacci_current

    return tribonacci_two

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Recognize that finding a number in this sequence relies on knowing the three numbers before it.
Start with the first three numbers of the sequence, which are already known.
To find the next number, simply add the three previous numbers that you already have.
Store this new number, so that you can use it in later calculations.
Repeat the adding and storing process until you reach the number you're looking for.
By keeping track of the numbers we've already calculated, we avoid repeating work and find the answer efficiently.

Code Implementation

def tribonacci(n):
    if n == 0:
        return 0
    if n == 1 or n == 2:
        return 1

    # Initialize the first three Tribonacci numbers.
    tribonacci_numbers = [0, 1, 1]

    # Iterate to calculate Tribonacci numbers up to n.
    for i in range(3, n + 1):
        # Calculate the next Tribonacci number.
        next_tribonacci_number = tribonacci_numbers[0] + tribonacci_numbers[1] + tribonacci_numbers[2]

        # Update the list to store the latest three numbers.
        tribonacci_numbers[0] = tribonacci_numbers[1]
        tribonacci_numbers[1] = tribonacci_numbers[2]
        tribonacci_numbers[2] = next_tribonacci_number

    # The last element is the nth Tribonacci number
    return tribonacci_numbers[2]

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n is 0	Return 0 as defined by T0 = 0.
n is 1	Return 1 as defined by T1 = 1.
n is 2	Return 1 as defined by T2 = 1.
n is a large positive integer	Use dynamic programming (iterative approach) to avoid recursion depth issues and optimize for time complexity.
Integer overflow for large n	Consider using a larger data type (e.g., long) or modulo operation if the problem specifies a modulo.
n is negative	Return an error or define the Tribonacci sequence for negative indices (uncommon, needs clarification).
n is a very large number that would exceed memory capacity when using DP array	Optimize space complexity by using only three variables to store the last three Tribonacci numbers.
Input is not an integer	Validate input type to ensure it is an integer.