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

दो प्रचुर संख्याओं के योग से न बनने वाली संख्याएँ

किसी सीमा तक की उन संख्याओं का योग निकालिए जिन्हें दो प्रचुर संख्याओं के योग के रूप में नहीं लिखा जा सकता।

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

  • Sieve से पूरी रेंज के भाजक-योग निकालना
  • Boolean array में संभव योगों पर निशान लगाना
  • योग सीमा पार करते ही दोहरे loop को बीच में रोकना

समस्या

कोई संख्या प्रचुर (abundant) तब होती है जब उसके उचित भाजकों (खुद को छोड़कर सभी भाजकों) का योग उससे ज़्यादा हो। 12 सबसे छोटी प्रचुर संख्या है: 1 + 2 + 3 + 4 + 6 = 16। कुछ संख्याएँ दो प्रचुर संख्याओं के योग के रूप में लिखी जा सकती हैं (एक ही संख्या दो बार भी ली जा सकती है, जैसे 24 = 12 + 12) और कुछ नहीं। 1 से limit तक के वे सभी धनात्मक पूर्णांक जोड़िए जो इस तरह नहीं लिखे जा सकते।

non_abundant_sums(limit) लिखिए।

sieve से सभी संख्याओं के भाजक-योग एक साथ निकालिए, प्रचुर संख्याओं की सूची बनाइए, फिर हर उस जोड़े के योग पर निशान लगाइए जो सीमा के भीतर रहता है।

इनपुट

limit: जाँची जाने वाली सबसे बड़ी संख्या।

आउटपुट

1 ≤ n ≤ limit वाले उन सभी n का योग लौटाइए जो दो प्रचुर संख्याओं का योग नहीं हैं।

सीमाएँ

1 ≤ limit ≤ 10,000

उदाहरण

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

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

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

अपेक्षित आउटपुट:
long expected = 276;

व्याख्या

कोई भी दो प्रचुर संख्याएँ मिलकर 23 या उससे छोटी संख्या नहीं बनातीं, इसलिए हर संख्या गिनी जाती है: 1 + 2 + ... + 23 = 276।

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

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

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

अपेक्षित आउटपुट:
long expected = 411;

व्याख्या

24 = 12 + 12 और 30 = 12 + 18 छूट जाते हैं, इसलिए उत्तर 465 − 24 − 30 = 411 है।

कैसे हल करें

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

संकेत 1

हर i के लिए 2i, 3i, 4i, ... के भाजक-योग में i जोड़िए।

संकेत 2

प्रचुर संख्याओं को बढ़ते क्रम में इकट्ठा कीजिए।

संकेत 3

हर जोड़े a ≤ b के लिए, जैसे ही a + b सीमा पार करे, भीतरी loop रोक दीजिए।

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

समय O(limit log limit + A²), जहाँ A प्रचुर संख्याओं की गिनती है, अतिरिक्त स्थान O(limit)

संदर्भ

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

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

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

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

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

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