समस्या
lo से hi तक हर a और हर b लेकर a^b निकालिए। कुछ मान दोहराते हैं, जैसे 2^4 = 4^2 = 16। गिनिए कि कितने अलग-अलग मान हैं। ये मान बहुत बड़े होते हैं, पर इन्हें निकालने की ज़रूरत ही नहीं: a को r^k के रूप में लिखिए, जहाँ r खुद किसी संख्या की पूर्ण घात न हो, तब a^b = r^(k × b)। दो घातें ठीक तब बराबर होती हैं जब उनका r और घातांक k × b दोनों एक जैसे हों।
distinct_powers(lo, hi) लिखिए।
इनपुट
lo: सबसे छोटा आधार और घातांक।
hi: सबसे बड़ा आधार और घातांक।
आउटपुट
lo ≤ a ≤ hi और lo ≤ b ≤ hi वाले a^b के अलग-अलग मानों की संख्या लौटाइए।
सीमाएँ
2 ≤ lo ≤ hi ≤ 100
उदाहरण
इनपुट:
lo = 2
hi = 4
अपेक्षित आउटपुट:
expected = 8
इनपुट:
long long lo = 2;
long long hi = 4;
अपेक्षित आउटपुट:
long long expected = 8;
इनपुट:
long lo = 2;
long hi = 4;
अपेक्षित आउटपुट:
long expected = 8;
व्याख्या
नौ घातें हैं 4, 8, 16, 9, 27, 81, 16, 64, 256। 16 दो बार आता है, इसलिए 8 अलग-अलग मान हैं।
इनपुट:
lo = 7
hi = 7
अपेक्षित आउटपुट:
expected = 1
इनपुट:
long long lo = 7;
long long hi = 7;
अपेक्षित आउटपुट:
long long expected = 1;
इनपुट:
long lo = 7;
long hi = 7;
अपेक्षित आउटपुट:
long expected = 1;
व्याख्या
सिर्फ़ 7^7 है, इसलिए 1।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
सबसे छोटा r और सबसे बड़ा k खोजिए जिनके लिए r^k = a हो।
संकेत 2
a^b = r^(k × b), इसलिए जोड़ा (r, k × b) मान को अलग से पहचान देता है।
संकेत 3
जोड़ों को एक set में डालिए और उन्हें गिनिए।
अपेक्षित जटिलता
समय O((hi − lo)² log hi), अतिरिक्त स्थान O((hi − lo)²)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।