Todos os desafios
Fácil 0 resolvidos 0% de aceitação

Palíndromos em duas bases

Some os números que se leem igual nos dois sentidos tanto na base 10 quanto em uma segunda base.

O que você vai aprender

  • Converter um número para qualquer base
  • Verificar se uma sequência é um palíndromo
  • Combinar duas condições de forma barata

Problema

Ver original (inglês)

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

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

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

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

Ainda não há soluções aprovadas. Resolva e fique com o primeiro lugar.

Aprenda com outros

Soluções da comunidade

Ainda não há soluções publicadas. Resolva este desafio para compartilhar a primeira.