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

Self Powers Tail

Find the last k digits of 1^1 + 2^2 + ... + n^n.

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

  • Reduce sums and products modulo 10^k
  • Compute powers with repeated squaring
  • Format a number with leading zeros

समस्या

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

The sum 1^1 + 2^2 + 3^3 + ... + n^n has thousands of digits even for modest n, but only its tail is needed. Find its last k digits. Work modulo 10^k from the start: reduce after every multiplication and every addition, and the numbers stay small.

Implement self_powers_tail(n, k).

Input

n: The last term of the sum.

k: How many trailing digits to return.

Output

Return the last k digits as a string of exactly k characters, padded with leading zeros if needed.

सीमाएँ

1 ≤ n ≤ 5000; 1 ≤ k ≤ 9

उदाहरण

उदाहरण 1
इनपुट:
n = 4
k = 3

अपेक्षित आउटपुट:
expected = "288"
इनपुट:
long long n = 4;
long long k = 3;

अपेक्षित आउटपुट:
std::string expected = "288";
इनपुट:
long n = 4;
long k = 3;

अपेक्षित आउटपुट:
string expected = "288";

व्याख्या

1 + 4 + 27 + 256 = 288, so the last three digits are "288".

उदाहरण 2
इनपुट:
n = 3
k = 4

अपेक्षित आउटपुट:
expected = "0032"
इनपुट:
long long n = 3;
long long k = 4;

अपेक्षित आउटपुट:
std::string expected = "0032";
इनपुट:
long n = 3;
long k = 4;

अपेक्षित आउटपुट:
string expected = "0032";

व्याख्या

1 + 4 + 27 = 32, padded to four digits: "0032".

कैसे हल करें

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

संकेत 1

Only the last k digits matter, so reduce modulo 10^k after every step.

संकेत 2

i^i can be found by repeated squaring, or by multiplying i times with reduction.

संकेत 3

Pad the final value on the left with zeros to get exactly k characters.

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

O(n log n) time, O(1) extra space

संदर्भ

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

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

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

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

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

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