Problema
Scrivi gli interi positivi uno dopo l'altro: 123456789101112131415... La posizione 1 contiene 1, la posizione 10 contiene l'1 di 10 e la posizione 11 lo 0 di 10. Per ogni posizione richiesta, trova la cifra che vi si trova. Le posizioni vanno ben oltre quello che potresti costruire come stringa: salta interi blocchi di numeri con lo stesso numero di cifre (9 numeri di una cifra, 90 di due cifre, 900 di tre cifre, ...).
Implementa champernowne_digits(positions).
Input
positions: posizioni nella stringa di cifre, contando da 1.
Output
Restituisci la cifra in ogni posizione, nello stesso ordine dell'input. Per un input vuoto restituisci una lista vuota.
Vincoli
0 ≤ positions.length ≤ 100; 1 ≤ posizione ≤ 10^15
Esempi
Input:
positions = [1, 9, 10, 11]
Output atteso:
expected = [1, 9, 1, 0]
Input:
std::vector<long long> positions = {1, 9, 10, 11};
Output atteso:
std::vector<long long> expected = {1, 9, 1, 0};
Input:
long[] positions = new long[] {1, 9, 10, 11};
Output atteso:
long[] expected = new long[] {1, 9, 1, 0};
Spiegazione
La stringa inizia con 1 2 3 4 5 6 7 8 9 1 0 1 1, quindi le cifre sono [1, 9, 1, 0].
Input:
positions = [15, 190]
Output atteso:
expected = [2, 1]
Input:
std::vector<long long> positions = {15, 190};
Output atteso:
std::vector<long long> expected = {2, 1};
Input:
long[] positions = new long[] {15, 190};
Output atteso:
long[] expected = new long[] {2, 1};
Spiegazione
La posizione 15 è il 2 di 12. Le posizioni da 10 a 189 contengono i numeri da 10 a 99, quindi la 190 è la prima cifra di 100: [2, 1].
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
I numeri con d cifre occupano in totale 9 × 10^(d − 1) × d posizioni.
Suggerimento 2
Sottrai blocchi interi finché la posizione non cade dentro uno di essi.
Suggerimento 3
Dentro il blocco, (position − 1) / d ti dice quale numero e (position − 1) % d quale cifra.
Complessità attesa
tempo O(m × log P) per m posizioni, spazio aggiuntivo O(m)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.