Условие

Числа Трибоначчи задаются так:

T0 = 0, T1 = 1, T2 = 1, и Tn+3 = Tn + Tn+1 + Tn+2 для n >= 0.

Найди n-е число Трибоначчи.

Примеры

Input: n = 4 Output: 4 Explanation: T3 = 2, T4 = 4

Input: n = 25 Output: 1389537

Решение

fun tribonacci(n: Int): Int {
    if (n == 0) return 0
    if (n == 1 || n == 2) return 1

    var a = 0
    var b = 1
    var c = 1
    var d = 0

    for (i in 3..n) {
        d = a + b + c  // сумма трёх предыдущих чисел
        a = b          // сдвигаем числа для следующего шага
        b = c
        c = d
    }

    return c
}

Временная сложность

O(n), где n — заданное число.

Пространственная сложность

O(1), дополнительной памяти почти нет.