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