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

स्व-घातों के योग के आख़िरी अंक

1^1 + 2^2 + ... + n^n के आख़िरी k अंक खोजिए।

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

  • योग और गुणनफल को modulo 10^k में घटाना
  • बार-बार वर्ग करके (repeated squaring) घात निकालना
  • संख्या को शुरुआती शून्यों के साथ लिखना

समस्या

योग 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

उदाहरण

उदाहरण 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, इसलिए आख़िरी तीन अंक "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, आगे शून्य जोड़कर चार अंक: "0032"।

कैसे हल करें

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

संकेत 1

सिर्फ़ आख़िरी k अंक मायने रखते हैं, इसलिए हर कदम के बाद modulo 10^k लीजिए।

संकेत 2

i^i को बार-बार वर्ग करके (repeated squaring) निकाला जा सकता है, या हर बार modulo लेते हुए i बार गुणा करके।

संकेत 3

ठीक k characters पाने के लिए अंतिम मान के बाईं ओर शून्य जोड़िए।

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

समय O(n log n), अतिरिक्त स्थान O(1)

संदर्भ

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

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

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

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

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

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