मध्यम 0 हल किए गए 0% स्वीकृति

Catalan Numbers

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

आप क्या सीखेंगे

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

समस्या

अनुवाद दिखाएँ

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.

सीमाएँ

0 ≤ n ≤ 35

उदाहरण

उदाहरण 1
इनपुट:
n = 4

अपेक्षित आउटपुट:
expected = [1, 1, 2, 5, 14]
इनपुट:
long long n = 4;

अपेक्षित आउटपुट:
std::vector<long long> expected = {1, 1, 2, 5, 14};
इनपुट:
long n = 4;

अपेक्षित आउटपुट:
long[] expected = new long[] {1, 1, 2, 5, 14};

व्याख्या

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

उदाहरण 2
इनपुट:
n = 0

अपेक्षित आउटपुट:
expected = [1]
इनपुट:
long long n = 0;

अपेक्षित आउटपुट:
std::vector<long long> expected = {1};
इनपुट:
long n = 0;

अपेक्षित आउटपुट:
long[] expected = new long[] {1};

व्याख्या

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

कैसे हल करें

पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।

संकेत 1

Store the values in a list as you compute them.

संकेत 2

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

संकेत 3

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

अपेक्षित जटिलता

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

संदर्भ

यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।

हर कोडर का सबसे अच्छा पास हुआ समाधान। तेज़, कम मेमोरी वाले और बेहतर रेटिंग वाले समाधान ऊपर रहते हैं।

अभी कोई पास हुआ समाधान नहीं है। इसे हल करें और पहला स्थान पाएँ।

दूसरों से सीखें

समुदाय समाधान

अभी तक कोई प्रकाशित समाधान नहीं। पहला साझा करने के लिए इस चुनौती को हल करें।