Todos los desafíos
Intermedio 0 resueltos 0% de aceptación

Cifras de la constante de Champernowne

Encuentra las cifras en ciertas posiciones de la cadena 123456789101112... que se forma al escribir seguidos los números naturales.

Lo que aprenderás

  • Contar las cifras que ocupan los números de cada longitud
  • Localizar el número y la cifra a partir de una posición
  • Usar aritmética de 64 bits de forma segura

Problema

Ver original (inglés)

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

Ejemplo 1
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].

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

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

Aún no hay soluciones aprobadas. Resuélvelo y quédate el primer puesto.

Aprende de otros

Soluciones de la comunidad

Aún no hay soluciones publicadas. Resuelve este reto para compartir la primera.