Medium 0 solved 0% acceptance

Catalan Numbers

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

What you'll learn

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

Problem

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.

Constraints

0 ≤ n ≤ 35

Examples

Example 1
Input:
n = 4

Expected output:
expected = [1, 1, 2, 5, 14]
Input:
long long n = 4;

Expected output:
std::vector<long long> expected = {1, 1, 2, 5, 14};
Input:
long n = 4;

Expected output:
long[] expected = new long[] {1, 1, 2, 5, 14};

Explanation

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

Example 2
Input:
n = 0

Expected output:
expected = [1]
Input:
long long n = 0;

Expected output:
std::vector<long long> expected = {1};
Input:
long n = 0;

Expected output:
long[] expected = new long[] {1};

Explanation

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

How to approach it

Try on your own first, then open one hint at a time.

Hint 1

Store the values in a list as you compute them.

Hint 2

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

Hint 3

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

Expected complexity

O(n^2) time, O(n) extra space

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

The best passing solution of each coder. Faster, smaller and better-reviewed solutions rank higher.

No passing solutions yet. Solve it to take first place.

Learn from others

Community solutions

No published solutions yet. Solve this challenge to share the first one.