Problema
Escribe los enteros positivos uno tras otro: 123456789101112131415... En la posición 1 está el 1, en la posición 10 el 1 del 10 y en la 11 el 0 del 10. Para cada posición pedida, encuentra la cifra que hay en ella. Las posiciones llegan mucho más lejos de lo que podrías construir como cadena: sáltate bloques completos de números con la misma cantidad de cifras (9 números de una cifra, 90 de dos cifras, 900 de tres cifras, ...).
Implementa champernowne_digits(positions).
Entrada
positions: posiciones en la cadena de cifras, contando desde 1.
Salida
Devuelve la cifra de cada posición, en el mismo orden que la entrada. Para una entrada vacía devuelve una lista vacía.
Restricciones
0 ≤ positions.length ≤ 100; 1 ≤ posición ≤ 10^15
Ejemplos
Entrada:
positions = [1, 9, 10, 11]
Salida esperada:
expected = [1, 9, 1, 0]
Entrada:
std::vector<long long> positions = {1, 9, 10, 11};
Salida esperada:
std::vector<long long> expected = {1, 9, 1, 0};
Entrada:
long[] positions = new long[] {1, 9, 10, 11};
Salida esperada:
long[] expected = new long[] {1, 9, 1, 0};
Explicación
La cadena empieza 1 2 3 4 5 6 7 8 9 1 0 1 1, así que las cifras son [1, 9, 1, 0].
Entrada:
positions = [15, 190]
Salida esperada:
expected = [2, 1]
Entrada:
std::vector<long long> positions = {15, 190};
Salida esperada:
std::vector<long long> expected = {2, 1};
Entrada:
long[] positions = new long[] {15, 190};
Salida esperada:
long[] expected = new long[] {2, 1};
Explicación
La posición 15 es el 2 del 12. Las posiciones de la 10 a la 189 corresponden a los números del 10 al 99, así que la 190 es la primera cifra del 100: [2, 1].
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Los números de d cifras ocupan en total 9 × 10^(d − 1) × d posiciones.
Pista 2
Resta bloques completos hasta que la posición caiga dentro de uno.
Pista 3
Dentro del bloque, (posición − 1) / d te dice qué número es y (posición − 1) % d qué cifra.
Complejidad esperada
tiempo O(m × log P) para m posiciones, espacio extra O(m)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.