सभी चुनौतियाँ
मध्यम 0 हल किए गए 0% स्वीकृति

कैटलन संख्याएँ

C(0) से C(n) तक की कैटलन संख्याओं की सूची बनाइए।

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

  • पिछले मानों से अनुक्रम बनाना
  • गुणनफलों के योग वाला पुनरावृत्ति संबंध इस्तेमाल करना
  • बीच के परिणामों में overflow से बचना

समस्या

कैटलन संख्याएँ 1, 1, 2, 5, 14, 42, … बहुत-सी चीज़ें गिनती हैं: n जोड़ी कोष्ठकों (parentheses) वाली संतुलित strings, n nodes वाले binary trees, और किसी उत्तल बहुभुज को त्रिभुजों में काटने के तरीके। ये C(0) = 1 से शुरू होती हैं और C(k + 1) = C(0)·C(k) + C(1)·C(k − 1) + … + C(k)·C(0) संबंध को पूरा करती हैं।

catalan_numbers(n) लिखिए।

इनपुट

n: सूची में शामिल होने वाली आख़िरी कैटलन संख्या का index।

आउटपुट

सूची [C(0), C(1), …, C(n)] लौटाइए, जिसमें n + 1 मान हैं। C(35) सबसे बड़ी संख्या है जो signed 64-bit पूर्णांक में समाती है, इसलिए बीच के चरणों में overflow का ध्यान रखिए।

सीमाएँ

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, इसलिए सूची [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};

व्याख्या

सिर्फ़ C(0) = 1 माँगा गया है: [1]।

कैसे हल करें

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

संकेत 1

मान निकालते समय उन्हें एक सूची में रखते जाइए।

संकेत 2

C(k + 1), i पर C(i) × C(k − i) का योग है।

संकेत 3

उस योग का हर गुणनफल अंतिम मान से बड़ा नहीं होता, इसलिए दी गई सीमाओं में यह तरीका कभी overflow नहीं करता।

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

समय O(n^2), अतिरिक्त स्थान O(n)

संदर्भ

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

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

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

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

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

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