Mittel 0 gelöst 0% Erfolgsquote

Catalan Numbers

List the Catalan numbers C(0) to C(n).

Das lernst du

  • Build a sequence from earlier values
  • Use a sum of products recurrence
  • Avoid overflow in intermediate results

Problem

Übersetzung anzeigen

The Catalan numbers 1, 1, 2, 5, 14, 42, … count many things: balanced strings of n pairs of parentheses, binary trees with n nodes, and ways to cut a convex polygon into triangles. They start with C(0) = 1 and satisfy C(k + 1) = C(0)·C(k) + C(1)·C(k − 1) + … + C(k)·C(0).

Implement catalan_numbers(n).

Input

n: The index of the last Catalan number to include.

Output

Return the list [C(0), C(1), …, C(n)], which has n + 1 values. C(35) is the largest that fits in a signed 64-bit integer, so watch out for overflow in intermediate steps.

Einschränkungen

0 ≤ n ≤ 35

Beispiele

Beispiel 1
Eingabe:
n = 4

Erwartete Ausgabe:
expected = [1, 1, 2, 5, 14]
Eingabe:
long long n = 4;

Erwartete Ausgabe:
std::vector<long long> expected = {1, 1, 2, 5, 14};
Eingabe:
long n = 4;

Erwartete Ausgabe:
long[] expected = new long[] {1, 1, 2, 5, 14};

Erläuterung

C(4) = 1·5 + 1·2 + 2·1 + 5·1 = 14, so the list is [1, 1, 2, 5, 14].

Beispiel 2
Eingabe:
n = 0

Erwartete Ausgabe:
expected = [1]
Eingabe:
long long n = 0;

Erwartete Ausgabe:
std::vector<long long> expected = {1};
Eingabe:
long n = 0;

Erwartete Ausgabe:
long[] expected = new long[] {1};

Erläuterung

Only C(0) = 1 is asked for: [1].

So gehst du vor

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

Hinweis 1

Store the values in a list as you compute them.

Hinweis 2

C(k + 1) is a sum over i of C(i) × C(k − i).

Hinweis 3

Each product in that sum is at most the final value, so the sum approach never overflows within the limits.

Erwartete Komplexität

O(n^2) time, O(n) 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.