Tutte le sfide
Facile 0 risolte 0% di accettazione

Palindromi in due basi

Somma i numeri che si leggono uguali nei due sensi sia in base 10 sia in una seconda base.

Cosa imparerai

  • Convertire un numero in una base qualsiasi
  • Verificare se una sequenza è palindroma
  • Combinare due condizioni in modo efficiente

Problema

Un palindromo si legge allo stesso modo da sinistra a destra e da destra a sinistra. 33 è palindromo in base 10, e in base 2 diventa 100001, di nuovo un palindromo. Somma tutti i numeri da 1 a limit che sono palindromi sia in base 10 sia in base base. I numeri si scrivono senza zeri iniziali.

Implementa double_base_palindromes(limit, base).

Input

limit: il numero più grande da controllare.

base: la seconda base.

Output

Restituisci la somma di tutti questi numeri.

Vincoli

1 ≤ limit ≤ 100 000; 2 ≤ base ≤ 16

Esempi

Esempio 1
Input:
limit = 10
base = 2

Output atteso:
expected = 25
Input:
long long limit = 10;
long long base = 2;

Output atteso:
long long expected = 25;
Input:
long limit = 10;
long base = 2;

Output atteso:
long expected = 25;

Spiegazione

1, 3, 5, 7 e 9 in base 2 sono 1, 11, 101, 111 e 1001, tutti palindromi; 2, 4, 6 e 8 no. Somma 25.

Esempio 2
Input:
limit = 50
base = 3

Output atteso:
expected = 15
Input:
long long limit = 50;
long long base = 3;

Output atteso:
long long expected = 15;
Input:
long limit = 50;
long base = 3;

Output atteso:
long expected = 15;

Spiegazione

In base 3 vanno bene 1, 2, 4 (11) e 8 (22), mentre 33 è 1020 e 44 è 1122. Somma 15.

Come affrontarlo

Prova prima da solo, poi apri un suggerimento alla volta.

Suggerimento 1

Le divisioni successive per la base danno le cifre dall'ultima alla prima.

Suggerimento 2

Per verificare un palindromo confronta la lista delle cifre con la stessa lista al contrario.

Suggerimento 3

Controlla prima la base 10: pochi numeri superano il test, quindi la seconda conversione serve di rado.

Complessità attesa

tempo O(limit × log limit), spazio aggiuntivo O(log limit)

Riferimenti

Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.

La migliore soluzione superata di ogni programmatore. Le più veloci, leggere e meglio valutate stanno in alto.

Ancora nessuna soluzione superata. Risolvila e prendi il primo posto.

Impara dagli altri

Soluzioni della community

Nessuna soluzione pubblicata. Risolvi questa sfida per condividere la prima.