Tutte le sfide
Media 0 risolte 0% di accettazione

Cifre di Champernowne

Trova le cifre in alcune posizioni della stringa 123456789101112... ottenuta scrivendo di seguito i numeri naturali.

Cosa imparerai

  • Contare le cifre usate dai numeri di ogni lunghezza
  • Individuare numero e cifra a partire da una posizione
  • Usare l'aritmetica a 64 bit in modo sicuro

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

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

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

La migliore soluzione superata di ogni programmatore. Le più veloci, leggere e meglio valutate stanno in alto.

Ancora nessuna soluzione superata. Risolvila e prendi il primo posto.

Impara dagli altri

Soluzioni della community

Nessuna soluzione pubblicata. Risolvi questa sfida per condividere la prima.