समस्या
योग 1^1 + 2^2 + 3^3 + ... + n^n में मामूली n के लिए भी हज़ारों अंक होते हैं, लेकिन हमें सिर्फ़ उसका आख़िरी हिस्सा चाहिए। इसके आख़िरी k अंक खोजिए। शुरू से ही modulo 10^k में काम कीजिए: हर गुणा और हर जोड़ के बाद modulo लीजिए, तो संख्याएँ छोटी ही रहेंगी।
self_powers_tail(n, k) लिखिए।
इनपुट
n: योग का आख़िरी पद।
k: आख़िर के कितने अंक लौटाने हैं।
आउटपुट
आख़िरी k अंकों को ठीक k characters की string के रूप में लौटाइए, ज़रूरत हो तो आगे शून्य जोड़कर।
सीमाएँ
1 ≤ n ≤ 5000; 1 ≤ k ≤ 9
उदाहरण
इनपुट:
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, इसलिए आख़िरी तीन अंक "288" हैं।
इनपुट:
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, आगे शून्य जोड़कर चार अंक: "0032"।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
सिर्फ़ आख़िरी k अंक मायने रखते हैं, इसलिए हर कदम के बाद modulo 10^k लीजिए।
संकेत 2
i^i को बार-बार वर्ग करके (repeated squaring) निकाला जा सकता है, या हर बार modulo लेते हुए i बार गुणा करके।
संकेत 3
ठीक k characters पाने के लिए अंतिम मान के बाईं ओर शून्य जोड़िए।
अपेक्षित जटिलता
समय O(n log n), अतिरिक्त स्थान O(1)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।