कठिन 0 हल किए गए 0% स्वीकृति

Non-Abundant Sums

Add up the numbers up to a limit that cannot be written as the sum of two abundant numbers.

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

  • Compute divisor sums for a range with a sieve
  • Mark reachable sums with a boolean array
  • Cut a double loop short once sums pass the limit

समस्या

अनुवाद दिखाएँ

A number is abundant when its proper divisors (all divisors except itself) add up to more than it. 12 is the smallest: 1 + 2 + 3 + 4 + 6 = 16. Some numbers can be written as the sum of two abundant numbers (the same one may be used twice, as in 24 = 12 + 12) and some cannot. Add up every positive integer from 1 to limit that cannot.

Implement non_abundant_sums(limit).

Find the divisor sums for every number at once with a sieve, list the abundant numbers, then mark every pair sum that stays within the limit.

Input

limit: The largest number to check.

Output

Return the sum of all n with 1 ≤ n ≤ limit that are not the sum of two abundant numbers.

सीमाएँ

1 ≤ limit ≤ 10,000

उदाहरण

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

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

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

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

व्याख्या

No two abundant numbers add up to 23 or less, so every number counts: 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 and 30 = 12 + 18 are left out, so the answer is 465 − 24 − 30 = 411.

कैसे हल करें

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

संकेत 1

For each i, add i to the divisor sum of 2i, 3i, 4i, ...

संकेत 2

Collect the abundant numbers in increasing order.

संकेत 3

For each pair a ≤ b, stop the inner loop once a + b passes the limit.

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

O(limit log limit + A²) time for A abundant numbers, O(limit) extra space

संदर्भ

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

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

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

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

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

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