Alle Herausforderungen
Einfach 0 gelöst 0% Erfolgsquote

Double-Base Palindromes

Add up the numbers that read the same both ways in base 10 and in a second base.

Das lernst du

  • Convert a number to any base
  • Check whether a sequence is a palindrome
  • Combine two conditions cheaply

Problem

Übersetzung anzeigen

A palindrome reads the same forwards and backwards. 33 is a palindrome in base 10, and in base 2 it is 100001, a palindrome again. Add up every number from 1 to limit that is a palindrome both in base 10 and in base base. Numbers are written without leading zeros.

Implement double_base_palindromes(limit, base).

Input

limit: The largest number to check.

base: The second base.

Output

Return the sum of all such numbers.

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 and 9 are 1, 11, 101, 111 and 1001 in base 2, all palindromes; 2, 4, 6 and 8 are not. Sum 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

In base 3: 1, 2, 4 (11) and 8 (22) qualify, while 33 is 1020 and 44 is 1122. Sum 15.

So gehst du vor

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

Hinweis 1

Repeated division by the base gives the digits from last to first.

Hinweis 2

A palindrome check compares the digit list with its reverse.

Hinweis 3

Check base 10 first: few numbers pass it, so the second conversion is rarely needed.

Erwartete Komplexität

O(limit × log limit) time, O(log limit) 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.