कठिन 0 हल किए गए 0% स्वीकृति

Digit Factorial Chains

Count starting numbers whose digit factorial chain has exactly a given number of distinct terms.

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

  • Follow a chain until a value repeats
  • Find chain lengths inside and before a loop
  • Reuse stored lengths

समस्या

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

Replace a number by the sum of the factorials of its digits: 145 gives 1! + 4! + 5! = 145 again, and 69 gives 6! + 9! = 363600. Repeating this always falls into a loop. The chain of a start is its terms until the first repeat: 69, 363600, 1454, 169, 363601 and then 1454 again, so 69 has 5 distinct terms. Count the starting numbers from 1 to limit whose chain has exactly length distinct terms.

Implement digit_factorial_chains(limit, length).

Many chains run into the same numbers. Store each number's chain length once it is known and reuse it.

Input

limit: The largest starting number.

length: The number of distinct terms wanted, the start included.

Output

Return how many starting numbers n with 1 ≤ n ≤ limit have exactly length distinct terms in their chain.

सीमाएँ

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 and 2! = 2, so 1 and 2 each map to themselves and have a chain of 1 term. The answer is 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 gives 6, then 720, 5043, ... so it is long. 10 gives 1! + 0! = 2 and then 2 again: two terms. Only 10 has exactly 2, so the answer is 1.

कैसे हल करें

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

संकेत 1

Precompute 0! to 9! once.

संकेत 2

Record each value's step number in the current chain; a repeat tells you where the loop starts.

संकेत 3

Values in the loop all have the loop's length, and each value before it has one more than the next.

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

O(limit × log limit) time with memoization, O(limit) extra space

संदर्भ

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

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

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

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

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

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