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

मित्र संख्याओं का जोड़ा

मित्र संख्याओं के वे सभी जोड़े बताइए जिनकी दोनों संख्याएँ दी गई सीमा से बड़ी न हों।

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

  • सीमा तक की हर संख्या के उचित भाजकों के योग की तालिका बनाना
  • जोड़े की शर्त दोनों दिशाओं में जाँचना
  • किसी जोड़े को दो बार या पूर्ण संख्याओं को जोड़े के रूप में लिखने से बचना

समस्या

मान लीजिए s(n) संख्या n के उचित भाजकों (ख़ुद n को छोड़कर उसके सभी भाजकों) का योग है। दो अलग-अलग संख्याएँ a और b मित्र संख्याओं का जोड़ा (amicable pair) बनाती हैं जब s(a) = b और s(b) = a हो। सबसे छोटा जोड़ा 220 और 284 है: s(220) = 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284 और s(284) = 1 + 2 + 4 + 71 + 142 = 220।

amicable_pair(limit) लिखिए।

limit तक की हर n के लिए s(n) एक-एक करके निकालना धीमा है। छलनी (sieve) बेहतर काम करती है: हर d के लिए, d से बड़े d के हर गुणज में d जोड़ दीजिए।

इनपुट

limit: किसी जोड़े की किसी भी संख्या का अधिकतम संभव मान।

आउटपुट

जोड़ों [a, b] की list लौटाइए, जहाँ a < b ≤ limit हो, और जोड़े a के आरोही क्रम में हों। कोई जोड़ा तभी शामिल होता है जब उसकी दोनों संख्याएँ limit से बड़ी न हों। पूर्ण संख्याएँ (जिनके लिए s(n) = n) जोड़ा नहीं मानी जातीं। कोई जोड़ा न हो तो खाली list लौटाइए।

सीमाएँ

1 ≤ limit ≤ 200,000

उदाहरण

उदाहरण 1
इनपुट:
limit = 1500

अपेक्षित आउटपुट:
expected = [
    [220, 284],
    [1184, 1210]
]
इनपुट:
long long limit = 1500;

अपेक्षित आउटपुट:
std::vector<std::vector<long long>> expected = {
    {220, 284},
    {1184, 1210}
};
इनपुट:
long limit = 1500;

अपेक्षित आउटपुट:
long[][] expected = new long[][] {
    new long[] {220, 284},
    new long[] {1184, 1210}
};

व्याख्या

s(220) = 284 और s(284) = 220, तथा s(1184) = 1210 और s(1210) = 1184। दोनों जोड़े 1500 के अंदर आते हैं: [[220, 284], [1184, 1210]]।

उदाहरण 2
इनपुट:
limit = 250

अपेक्षित आउटपुट:
expected = []
इनपुट:
long long limit = 250;

अपेक्षित आउटपुट:
std::vector<std::vector<long long>> expected = {};
इनपुट:
long limit = 250;

अपेक्षित आउटपुट:
long[][] expected = new long[][] {};

व्याख्या

220 तो 250 से बड़ा नहीं है, लेकिन उसका साथी 284 बड़ा है, इसलिए कोई जोड़ा नहीं बनता: []।

कैसे हल करें

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

संकेत 1

1 से limit / 2 तक के हर d के लिए, 2d, 3d, 4d और आगे के योगों में d जोड़िए।

संकेत 2

हर a के लिए b को उसके भाजकों का योग मानिए, और जाँचिए कि b सीमा के अंदर है और b के भाजकों का योग a है।

संकेत 3

a < b की शर्त से हर जोड़ा एक ही बार आता है और पूर्ण संख्याएँ अपने-आप छूट जाती हैं।

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

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

संदर्भ

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

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

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

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

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

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