मध्यम 0 हल किए गए 0% स्वीकृति

Pentagonal Pair

Count pairs of pentagonal numbers whose sum is pentagonal too.

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

  • Generate pentagonal numbers
  • Test membership with a formula
  • Count pairs with a double loop

समस्या

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

Pentagonal numbers are P(k) = k(3k − 1) / 2: 1, 5, 12, 22, 35, 51, 70, ... Some pairs add up to another pentagonal number, like P(4) + P(7) = 22 + 70 = 92 = P(8). Count the pairs j < k ≤ n for which P(j) + P(k) is pentagonal. A quick test helps: x is pentagonal exactly when 24x + 1 is a perfect square s² with s % 6 = 5.

Implement pentagonal_pair(n).

Input

n: The largest index k to use.

Output

Return the number of pairs (j, k) with 1 ≤ j < k ≤ n and P(j) + P(k) pentagonal.

सीमाएँ

1 ≤ n ≤ 1000

उदाहरण

उदाहरण 1
इनपुट:
n = 7

अपेक्षित आउटपुट:
expected = 1
इनपुट:
long long n = 7;

अपेक्षित आउटपुट:
long long expected = 1;
इनपुट:
long n = 7;

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

व्याख्या

Of the 21 pairs up to k = 7, only P(4) + P(7) = 92 = P(8) is pentagonal, so the answer is 1.

उदाहरण 2
इनपुट:
n = 1

अपेक्षित आउटपुट:
expected = 0
इनपुट:
long long n = 1;

अपेक्षित आउटपुट:
long long expected = 0;
इनपुट:
long n = 1;

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

व्याख्या

There is no pair with j < k ≤ 1, so the answer is 0.

कैसे हल करें

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

संकेत 1

P(k) = k(3k − 1) / 2.

संकेत 2

Check 24x + 1 for a perfect square with an integer square root, then check the root modulo 6.

संकेत 3

Only pairs with j < k are counted.

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

O(n²) time, O(n) extra space

संदर्भ

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

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

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

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

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

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