Einfach 0 gelöst 0% Erfolgsquote

Tribonacci

Return the nth tribonacci number, where each term is the sum of the three before it.

Das lernst du

  • Compute a sequence iteratively
  • Keep only the last few terms
  • Handle the starting terms directly

Problem

Übersetzung anzeigen

The tribonacci numbers extend the Fibonacci idea to three terms: T(0) = 0, T(1) = 0, T(2) = 1, and from then on T(n) = T(n − 1) + T(n − 2) + T(n − 3). The sequence goes 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, …

Implement tribonacci(n).

Input

n: The index of the term, starting at 0.

Output

Return T(n). Only the last three terms are needed at any time, so a loop with three variables is enough.

Einschränkungen

0 ≤ n ≤ 74

Beispiele

Beispiel 1
Eingabe:
n = 7

Erwartete Ausgabe:
expected = 13
Eingabe:
long long n = 7;

Erwartete Ausgabe:
long long expected = 13;
Eingabe:
long n = 7;

Erwartete Ausgabe:
long expected = 13;

Erläuterung

The terms are 0, 0, 1, 1, 2, 4, 7, 13, so T(7) = 13.

Beispiel 2
Eingabe:
n = 2

Erwartete Ausgabe:
expected = 1
Eingabe:
long long n = 2;

Erwartete Ausgabe:
long long expected = 1;
Eingabe:
long n = 2;

Erwartete Ausgabe:
long expected = 1;

Erläuterung

T(2) is the first 1 in the sequence: 1.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Return the first three terms directly.

Hinweis 2

Keep three variables and shift them along each step.

Hinweis 3

A recursive solution without memory repeats work and is far too slow.

Erwartete Komplexität

O(n) time, O(1) extra space

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.