Mittel 0 gelöst 0% Erfolgsquote

Pentagonal Pair

Count pairs of pentagonal numbers whose sum is pentagonal too.

Das lernst du

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

Problem

Übersetzung anzeigen

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.

Einschränkungen

1 ≤ n ≤ 1000

Beispiele

Beispiel 1
Eingabe:
n = 7

Erwartete Ausgabe:
expected = 1
Eingabe:
long long n = 7;

Erwartete Ausgabe:
long long expected = 1;
Eingabe:
long n = 7;

Erwartete Ausgabe:
long expected = 1;

Erläuterung

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

Beispiel 2
Eingabe:
n = 1

Erwartete Ausgabe:
expected = 0
Eingabe:
long long n = 1;

Erwartete Ausgabe:
long long expected = 0;
Eingabe:
long n = 1;

Erwartete Ausgabe:
long expected = 0;

Erläuterung

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

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

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

Hinweis 2

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

Hinweis 3

Only pairs with j < k are counted.

Erwartete Komplexität

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

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.