Problema
Um palíndromo é lido da mesma forma de frente para trás e de trás para frente. 33 é um palíndromo na base 10 e, na base 2, é 100001, outro palíndromo. Some todos os números de 1 a limit que são palíndromos tanto na base 10 quanto na base base. Os números são escritos sem zeros à esquerda.
Implemente double_base_palindromes(limit, base).
Entrada
limit: o maior número a verificar.
base: a segunda base.
Saída
Retorne a soma de todos esses números.
Restrições
1 ≤ limit ≤ 100 000; 2 ≤ base ≤ 16
Exemplos
Entrada:
limit = 10
base = 2
Saída esperada:
expected = 25
Entrada:
long long limit = 10;
long long base = 2;
Saída esperada:
long long expected = 25;
Entrada:
long limit = 10;
long base = 2;
Saída esperada:
long expected = 25;
Explicação
1, 3, 5, 7 e 9 são 1, 11, 101, 111 e 1001 na base 2, todos palíndromos; 2, 4, 6 e 8 não são. Soma 25.
Entrada:
limit = 50
base = 3
Saída esperada:
expected = 15
Entrada:
long long limit = 50;
long long base = 3;
Saída esperada:
long long expected = 15;
Entrada:
long limit = 50;
long base = 3;
Saída esperada:
long expected = 15;
Explicação
Na base 3: 1, 2, 4 (11) e 8 (22) se encaixam, enquanto 33 é 1020 e 44 é 1122. Soma 15.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Divisões sucessivas pela base dão os dígitos do último para o primeiro.
Dica 2
Para verificar um palíndromo, compare a lista de dígitos com a sua inversa.
Dica 3
Verifique a base 10 primeiro: poucos números passam, então a segunda conversão raramente é necessária.
Complexidade esperada
tempo O(limit × log limit), espaço extra O(log limit)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.