1137. N-th Tribonacci Number

Sum of paths from root to leaf

Compute the $n$-th tribonacci number.

Intuition

Same as compute the $n$-th fibonacci number, we use three numbers to remember the state.

Approach

We use three numbers to represent $n-2$, $n-1$ and $n$-th tribonacci number respectively

Complexity

Time complexity: $$O(n)$$
Space complexity: $$O(1)$$

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    int tribonacci(int n) {
        vector<int> nums{0, 1, 1};
        if (n < 3)  return nums[n];
        for (int i = 2; i < n; ++i) {
            int temp = nums[2];
            nums[2] += nums[0] + nums[1];
            nums[0] = nums[1];
            nums[1] = temp;
        }
        return nums[2];
    }
};

comments powered by Disqus