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

अंकों के फ़ैक्टोरियल की श्रृंखलाएँ

वे आरंभिक संख्याएँ गिनिए जिनकी अंक-फ़ैक्टोरियल श्रृंखला में ठीक दी गई संख्या जितने अलग-अलग पद हों।

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

  • किसी मान के दोहराए जाने तक श्रृंखला पर चलना
  • चक्र के भीतर और उससे पहले की श्रृंखला-लंबाइयाँ निकालना
  • सहेजी गई लंबाइयों का दोबारा इस्तेमाल करना

समस्या

किसी संख्या की जगह उसके अंकों के फ़ैक्टोरियल का योग रखिए: 145 से 1! + 4! + 5! = 145 ही मिलता है, और 69 से 6! + 9! = 363600। ऐसा बार-बार करने पर हमेशा कोई चक्र (loop) बन जाता है। किसी शुरुआती संख्या की श्रृंखला उसके वे पद हैं जो पहली बार कोई पद दोहराए जाने से पहले आते हैं: 69, 363600, 1454, 169, 363601 और फिर दोबारा 1454, इसलिए 69 के 5 अलग-अलग पद हैं। 1 से limit तक की वे आरंभिक संख्याएँ गिनिए जिनकी श्रृंखला में ठीक length अलग-अलग पद हों।

digit_factorial_chains(limit, length) लिखिए।

कई श्रृंखलाएँ एक ही संख्याओं से होकर गुज़रती हैं। किसी संख्या की श्रृंखला-लंबाई पता चलते ही उसे सहेज लीजिए और आगे दोबारा इस्तेमाल कीजिए।

इनपुट

limit: सबसे बड़ी आरंभिक संख्या।

length: कितने अलग-अलग पद चाहिए, शुरुआती संख्या समेत।

आउटपुट

लौटाइए कि 1 ≤ n ≤ limit वाली कितनी आरंभिक संख्याओं n की श्रृंखला में ठीक length अलग-अलग पद हैं।

सीमाएँ

1 ≤ limit ≤ 100,000; 1 ≤ length ≤ 70

उदाहरण

उदाहरण 1
इनपुट:
limit = 2
length = 1

अपेक्षित आउटपुट:
expected = 2
इनपुट:
long long limit = 2;
long long length = 1;

अपेक्षित आउटपुट:
long long expected = 2;
इनपुट:
long limit = 2;
long length = 1;

अपेक्षित आउटपुट:
long expected = 2;

व्याख्या

1! = 1 और 2! = 2, इसलिए 1 और 2 दोनों खुद पर ही लौट आते हैं और उनकी श्रृंखला में 1 पद है। उत्तर 2 है।

उदाहरण 2
इनपुट:
limit = 10
length = 2

अपेक्षित आउटपुट:
expected = 1
इनपुट:
long long limit = 10;
long long length = 2;

अपेक्षित आउटपुट:
long long expected = 1;
इनपुट:
long limit = 10;
long length = 2;

अपेक्षित आउटपुट:
long expected = 1;

व्याख्या

3 से 6 मिलता है, फिर 720, 5043, ... इसलिए यह श्रृंखला लंबी है। 10 से 1! + 0! = 2 मिलता है और फिर दोबारा 2, यानी दो पद। सिर्फ़ 10 के ठीक 2 पद हैं, इसलिए उत्तर 1 है।

कैसे हल करें

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

संकेत 1

0! से 9! तक एक बार पहले से निकालकर रख लीजिए।

संकेत 2

मौजूदा श्रृंखला में हर मान का कदम नंबर दर्ज कीजिए; कोई मान दोहराए तो पता चल जाता है कि चक्र कहाँ से शुरू होता है।

संकेत 3

चक्र के सभी मानों की लंबाई चक्र की लंबाई के बराबर होती है, और चक्र से पहले वाले हर मान की लंबाई अपने अगले मान से एक ज़्यादा होती है।

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

समय O(limit × log limit) memoization के साथ, अतिरिक्त स्थान O(limit)

संदर्भ

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

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

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

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

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

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