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
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.
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.