Tribonacci Number in Python (O(n) Time, O(1) Space)
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 sums the last three numbers instead of the last two. This sequence has applications in various mathematical and computational problems.
Approach
To solve this problem, we can use an iterative approach to keep track of the last three numbers in the sequence. This allows us to compute the next number in constant time and space.
Naive Solution
A naive solution would involve using recursion to compute the Tribonacci number. However, this approach is highly inefficient due to repeated calculations, leading to exponential time complexity.
Optimized Solution
An optimized solution involves using an iterative approach with three variables to keep track of the last three numbers in the sequence. This approach ensures O(n) time complexity and O(1) space complexity.
Algorithm
1. Initialize three variables to store the first three Tribonacci numbers: T0 = 0, T1 = 1, T2 = 1.
2. Iterate from 3 to n, updating the variables to store the last three numbers in the sequence.
3. Return the nth Tribonacci number.
Code Implementation
def tribonacci(n):
# Base cases
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
# Iterate from 3 to n
for i in range(3, n + 1):
# Calculate the next Tribonacci number
Tn = T0 + T1 + T2
# Update the variables
T0, T1, T2 = T1, T2, Tn
return T2
# Example usage
print(tribonacci(3)) # Output: 2
print(tribonacci(4)) # Output: 4
print(tribonacci(5)) # Output: 7
Complexity Analysis
The time complexity of this approach is O(n) because we iterate from 3 to n. The space complexity is O(1) because we only use a constant amount of space to store the last three numbers in the sequence.
Edge Cases
1. n = 0: The output should be 0.
2. n = 1 or n = 2: The output should be 1.
3. Large values of n: The algorithm should handle large values efficiently due to its linear time complexity.
Testing
To test the solution comprehensively, we can use a variety of test cases:
def test_tribonacci():
assert tribonacci(0) == 0
assert tribonacci(1) == 1
assert tribonacci(2) == 1
assert tribonacci(3) == 2
assert tribonacci(4) == 4
assert tribonacci(5) == 7
assert tribonacci(10) == 149
assert tribonacci(25) == 1389537
print("All test cases pass")
test_tribonacci()
Thinking and Problem-Solving Tips
1. Break down the problem into smaller parts and understand the sequence's properties.
2. Consider edge cases and how the algorithm handles them.
3. Practice similar problems to improve problem-solving skills.
Conclusion
Understanding and solving the Tribonacci number problem helps improve algorithmic thinking and problem-solving skills. The iterative approach ensures efficient computation with linear time complexity and constant space complexity.
Additional Resources
1. Generalizations of Fibonacci numbers