Alle Herausforderungen
Einfach 0 gelöst 0% Erfolgsquote

Palindrome in zwei Zahlensystemen

Addiere die Zahlen, die im Zehnersystem und in einer zweiten Basis vorwärts wie rückwärts gleich lauten.

Das lernst du

  • Eine Zahl in eine beliebige Basis umrechnen
  • Prüfen, ob eine Folge ein Palindrom ist
  • Zwei Bedingungen geschickt und günstig kombinieren

Problem

Ein Palindrom liest sich vorwärts und rückwärts gleich. 33 ist im Zehnersystem ein Palindrom, und zur Basis 2 lautet es 100001, wieder ein Palindrom. Addiere alle Zahlen von 1 bis limit, die sowohl zur Basis 10 als auch zur Basis base Palindrome sind. Die Zahlen werden ohne führende Nullen geschrieben.

Implementiere double_base_palindromes(limit, base).

Eingabe

limit: Die größte zu prüfende Zahl.

base: Die zweite Basis.

Ausgabe

Gib die Summe all dieser Zahlen zurück.

Einschränkungen

1 ≤ limit ≤ 100.000; 2 ≤ base ≤ 16

Beispiele

Beispiel 1
Eingabe:
limit = 10
base = 2

Erwartete Ausgabe:
expected = 25
Eingabe:
long long limit = 10;
long long base = 2;

Erwartete Ausgabe:
long long expected = 25;
Eingabe:
long limit = 10;
long base = 2;

Erwartete Ausgabe:
long expected = 25;

Erläuterung

1, 3, 5, 7 und 9 lauten zur Basis 2 1, 11, 101, 111 und 1001, alles Palindrome, 2, 4, 6 und 8 dagegen nicht. Summe 25.

Beispiel 2
Eingabe:
limit = 50
base = 3

Erwartete Ausgabe:
expected = 15
Eingabe:
long long limit = 50;
long long base = 3;

Erwartete Ausgabe:
long long expected = 15;
Eingabe:
long limit = 50;
long base = 3;

Erwartete Ausgabe:
long expected = 15;

Erläuterung

Zur Basis 3 erfüllen 1, 2, 4 (11) und 8 (22) die Bedingung, 33 lautet dort dagegen 1020 und 44 lautet 1122. Summe 15.

So gehst du vor

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

Hinweis 1

Fortgesetzte Division durch die Basis liefert die Ziffern von hinten nach vorn.

Hinweis 2

Für den Palindromtest vergleichst du die Ziffernliste mit ihrer Umkehrung.

Hinweis 3

Prüfe zuerst die Basis 10: Nur wenige Zahlen bestehen diesen Test, die zweite Umrechnung ist also selten nötig.

Erwartete Komplexität

Zeit O(limit × log limit), zusätzlicher Speicher O(log limit)

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.