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
2
3
4

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};
public int tribonacci(int n) {
    return nums[n];
}

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. 😉😃💗