समस्या
2 की घातें बहुत तेज़ी से बढ़ती हैं: 2^64 में ही 20 अंक हैं और 2^2000 में 600 से ज़्यादा। 2^n को बिल्कुल सही निकालिए और उसके दशमलव अंक जोड़िए। अगर बड़े पूर्णांक (big integers) उपलब्ध न हों, तो संख्या को अंकों के array के रूप में रखिए और उसे n बार दोगुना कीजिए।
digit_sum_power_of_two(n) लिखिए।
इनपुट
n: घातांक।
आउटपुट
2^n के दशमलव अंकों का योग लौटाइए।
सीमाएँ
0 ≤ n ≤ 2000
उदाहरण
इनपुट:
n = 10
अपेक्षित आउटपुट:
expected = 7
इनपुट:
long long n = 10;
अपेक्षित आउटपुट:
long long expected = 7;
इनपुट:
long n = 10;
अपेक्षित आउटपुट:
long expected = 7;
व्याख्या
2^10 = 1024 और 1 + 0 + 2 + 4 = 7।
इनपुट:
n = 0
अपेक्षित आउटपुट:
expected = 1
इनपुट:
long long n = 0;
अपेक्षित आउटपुट:
long long expected = 1;
इनपुट:
long n = 0;
अपेक्षित आउटपुट:
long expected = 1;
व्याख्या
2^0 = 1, इसलिए अंकों का योग 1 है।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
2^n का मतलब है 1 को n बार दोगुना करना।
संकेत 2
अंकों को सबसे निचले अंक से शुरू करके रखिए, ताकि हासिल array के आख़िर की ओर बढ़े।
संकेत 3
अंकों का योग तभी निकालिए जब दोगुना करना पूरा हो जाए।
अपेक्षित जटिलता
समय O(n²), अतिरिक्त स्थान O(n)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।