समस्या
ट्रिबोनाची संख्याएँ फ़िबोनाची वाले विचार को तीन पदों तक ले जाती हैं: T(0) = 0, T(1) = 0, T(2) = 1, और उसके बाद T(n) = T(n − 1) + T(n − 2) + T(n − 3)। अनुक्रम इस तरह चलता है: 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, …
tribonacci(n) लिखिए।
इनपुट
n: पद का index, जो 0 से शुरू होता है।
आउटपुट
T(n) लौटाइए। किसी भी समय सिर्फ़ आख़िरी तीन पदों की ज़रूरत होती है, इसलिए तीन variables वाला एक loop काफ़ी है।
सीमाएँ
0 ≤ n ≤ 74
उदाहरण
इनपुट:
n = 7
अपेक्षित आउटपुट:
expected = 13
इनपुट:
long long n = 7;
अपेक्षित आउटपुट:
long long expected = 13;
इनपुट:
long n = 7;
अपेक्षित आउटपुट:
long expected = 13;
व्याख्या
पद हैं 0, 0, 1, 1, 2, 4, 7, 13, इसलिए T(7) = 13।
इनपुट:
n = 2
अपेक्षित आउटपुट:
expected = 1
इनपुट:
long long n = 2;
अपेक्षित आउटपुट:
long long expected = 1;
इनपुट:
long n = 2;
अपेक्षित आउटपुट:
long expected = 1;
व्याख्या
T(2) अनुक्रम का पहला 1 है: 1।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
पहले तीन पद सीधे लौटा दीजिए।
संकेत 2
तीन variables रखिए और हर कदम पर उन्हें एक-एक स्थान आगे खिसकाइए।
संकेत 3
बिना memory वाला recursive हल एक ही काम बार-बार करता है और बहुत धीमा है।
अपेक्षित जटिलता
समय O(n), अतिरिक्त स्थान O(1)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।