Tribonacci Number in O(n) Time and O(1) Space using C++

The Tribonacci numbers, commonly denoted T(n) form a sequence, called the Tribonacci sequence, such that each number is the sum of the two preceding ones, starting from 0, 1 and 1. That is,

T(0) = 0, T(1) = 1, T(2) = 1
T(n) = T(n - 1) + T(n - 2) + T(n - 3), for n > 2.

Given n, calculate and return T(n).

Example 1:

Input: n = 3
Output: 2
Explanation: T(3) = T(2) + T(1) + T(0) = 1 + 1 + 0 = 2.

Example 2:

Input: n = 4
Output: 4
Explanation: T(4) = T(3) + T(2) + T(1) = 2 + 1 + 1 = 4.

Example 3:

Input: n = 5
Output: 7
Explanation: T(5) = T(4) + T(3) + T(2) = 4 + 2 + 1 = 7.

Note:

Your algorithm should run in O(n) time and use O(1) space.

Understanding the Problem

The core challenge of this problem is to compute the nth Tribonacci number efficiently. The Tribonacci sequence is similar to the Fibonacci sequence but instead of summing the last two numbers, we sum the last three numbers. This problem is significant in various applications such as dynamic programming and algorithm optimization.

Approach

To solve this problem, we can start with a naive recursive solution, but it will be highly inefficient due to repeated calculations. Instead, we can use an iterative approach to achieve O(n) time complexity and O(1) space complexity.

Naive Recursive Solution

The naive approach involves recursively calculating T(n) by summing T(n-1), T(n-2), and T(n-3). However, this approach has exponential time complexity due to overlapping subproblems.

Optimized Iterative Solution

We can optimize the solution by using an iterative approach with three variables to keep track of the last three Tribonacci numbers. This way, we can compute T(n) in O(n) time and O(1) space.

Algorithm

1. Initialize three variables to store T(0), T(1), and T(2).

2. Iterate from 3 to n, updating the three variables to store the last three Tribonacci numbers.

3. Return the nth Tribonacci number.

Code Implementation


#include <iostream>
using namespace std;

// Function to calculate the nth Tribonacci number
int tribonacci(int n) {
    // Base cases
    if (n == 0) return 0;
    if (n == 1 || n == 2) return 1;

    // Initialize the first three Tribonacci numbers
    int t0 = 0, t1 = 1, t2 = 1;

    // Variable to store the current Tribonacci number
    int tn;

    // Iterate from 3 to n
    for (int i = 3; i <= n; ++i) {
        // Calculate the current Tribonacci number
        tn = t0 + t1 + t2;

        // Update the last three Tribonacci numbers
        t0 = t1;
        t1 = t2;
        t2 = tn;
    }

    // Return the nth Tribonacci number
    return tn;
}

int main() {
    // Test cases
    cout << "T(3) = " << tribonacci(3) << endl; // Output: 2
    cout << "T(4) = " << tribonacci(4) << endl; // Output: 4
    cout << "T(5) = " << tribonacci(5) << endl; // Output: 7
    return 0;
}

Complexity Analysis

The time complexity of the optimized iterative solution is O(n) because we iterate from 3 to n. The space complexity is O(1) because we only use a constant amount of extra space to store the last three Tribonacci numbers.

Edge Cases

1. n = 0: The output should be 0.

2. n = 1: The output should be 1.

3. n = 2: The output should be 1.

These edge cases are handled by the base cases in the code.

Testing

To test the solution comprehensively, we should include a variety of test cases:

Small values of n (e.g., 0, 1, 2, 3, 4, 5)
Large values of n to test the efficiency (e.g., 30, 50, 100)
Edge cases as mentioned above

Thinking and Problem-Solving Tips

When approaching such problems, it's essential to:

Understand the problem statement and constraints thoroughly.
Start with a naive solution to get a basic understanding.
Identify the inefficiencies in the naive solution and think of ways to optimize it.
Consider using iterative approaches and dynamic programming to improve efficiency.

Conclusion

In this blog post, we discussed the Tribonacci number problem, understood its significance, and explored various approaches to solve it. We provided an optimized iterative solution in C++ with detailed explanations and complexity analysis. Understanding and solving such problems is crucial for improving problem-solving skills and algorithmic thinking.

Additional Resources

For further reading and practice, consider the following resources: