समस्या
कैटलन संख्याएँ 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
उदाहरण
इनपुट:
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] है।
इनपुट:
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 के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।