Statement

Tribonacci numbers are a sequence of numbers where each number is the sum of the three preceding numbers. Your task is to find the nthn^{th} Tribonacci number.

The Tribonacci sequence is defined as:

T0=0, T1=1, T2=1T_0 = 0,\space T_1 = 1,\space T_2 = 1, and  Tn=Tn1+Tn2+Tn3, \space T_n = T_{n-1} + T_{n-2} + T_{n-3}, \space for n>=3n >= 3

The input number, n, is a non-negative integer.

Let’s say you have to find the fifth Tribonacci number in the sequence. From the sequence defined above, we know that T0=0,T1=1,T2=1T_0 = 0, T_1 = 1, T_2 = 1. The sequence will be:

0,1,1,2,4,70, 1, 1, 2, 4, 7

Therefore, the fifth term will be 7.

Constraints:

  • 00 \leq n 73\leq 73
  • The answer is guaranteed to fit within a 64-bit integer, i.e., answer 2631\leq 2 ^{63} - 1

Examples

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.