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