[LeetCode][1137. N-th Tribonacci Number] Any Language Beats 100% | Time O(1) Solution
By Long Luo
This article is the solution Any Language Beats 100% with Time O(1) Solution of Problem 1137. N-th Tribonacci Number.
Lookup Table
\(32\) bit signed integers only.
If we don’t need to solve very large values and are time-sensitive, we can find all values in advance.
This function will work strictly in the case that we’re dealing with \(32\) bit signed integers (which could be a constraint in languages like Java, C/C++, etc.)
The tribonacci sequence grows very quickly, which means that only the first 37 tribonacci numbers fit within the range of a \(32\) bit signed integer.
This method requires only a quick list lookup to find the nth tribonacci number, so it runs in constant time. Since the list is of fixed length, this method runs in constant space as well.
1 | int[] nums = {0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, 121415, 223317, 410744, 755476, 1389537, 2555757, 4700770, 8646064, 15902591, 29249425, 53798080, 98950096, 181997601, 334745777, 615693474, 1132436852, 2082876103}; |
Analysis
- Time Complexity: \(O(1)\).
- Space Complexity: \(O(1)\).
All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗