< Back




1137. N-th Tribonacci Number

Like Fibonacci, but with three numbers instead of two.

The solution is as follows:


  class Solution:
      def tribonacci(self, n: int) -> int:
          if n < 3:
              return 1 if n else 0

          a, b, c = 0, 1, 1

          for _ in range(3, n + 1):
              a, b, c = b, c, a + b + c

          return c


_ Time Complexity:

  O(n) - Where n is the input number, we iterate n times.

_ Space Complexity:

  O(1) - We use three integers variables, taking constant space to memoize the
  three numbers for the Tribonacci sequenece.