Todos os desafios
Médio 0 resolvidos 0% de aceitação

Dígitos de Champernowne

Encontre os dígitos em posições dadas da sequência 123456789101112... formada ao escrever os números naturais em seguida.

O que você vai aprender

  • Contar os dígitos usados pelos números de cada tamanho
  • Localizar o número e o dígito a partir de uma posição
  • Usar aritmética de 64 bits com segurança

Problema

Ver original (inglês)

Escreva os inteiros positivos um após o outro: 123456789101112131415... A posição 1 tem o 1, a posição 10 tem o 1 do 10 e a posição 11, o 0 do 10. Para cada posição pedida, encontre o dígito que está nela. As posições vão muito além do que daria para montar como string: pule blocos inteiros de números com a mesma quantidade de dígitos (9 números de um dígito, 90 de dois dígitos, 900 de três dígitos, ...).

Implemente champernowne_digits(positions).

Entrada

positions: posições na sequência de dígitos, contando a partir de 1.

Saída

Retorne o dígito de cada posição, na mesma ordem da entrada. Uma entrada vazia retorna uma lista vazia.

Restrições

0 ≤ positions.length ≤ 100; 1 ≤ posição ≤ 10^15

Exemplos

Exemplo 1
Entrada:
positions = [1, 9, 10, 11]

Saída esperada:
expected = [1, 9, 1, 0]
Entrada:
std::vector<long long> positions = {1, 9, 10, 11};

Saída esperada:
std::vector<long long> expected = {1, 9, 1, 0};
Entrada:
long[] positions = new long[] {1, 9, 10, 11};

Saída esperada:
long[] expected = new long[] {1, 9, 1, 0};

Explicação

A sequência começa com 1 2 3 4 5 6 7 8 9 1 0 1 1, então os dígitos são [1, 9, 1, 0].

Exemplo 2
Entrada:
positions = [15, 190]

Saída esperada:
expected = [2, 1]
Entrada:
std::vector<long long> positions = {15, 190};

Saída esperada:
std::vector<long long> expected = {2, 1};
Entrada:
long[] positions = new long[] {15, 190};

Saída esperada:
long[] expected = new long[] {2, 1};

Explicação

A posição 15 é o 2 do 12. As posições de 10 a 189 contêm os números de 10 a 99, então a 190 é o primeiro dígito do 100: [2, 1].

Como abordar

Tente sozinho primeiro e depois abra uma dica de cada vez.

Dica 1

Os números de d dígitos ocupam, ao todo, 9 × 10^(d − 1) × d posições.

Dica 2

Subtraia blocos inteiros até a posição cair dentro de um deles.

Dica 3

Dentro do bloco, (position − 1) / d diz qual é o número e (position − 1) % d diz qual é o dígito.

Complexidade esperada

tempo O(m × log P) para m posições, espaço extra O(m)

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.