Count Digits
Scrivi una funzione che riceve un intero non negativo n e restituisce quante cifre ha quando lo scrivi in base 10 senza zeri iniziali. Lo zero si scrive come un singolo 0, quindi ha una cifra.
Funzione
- ninteger
- l'intero non negativo da misurare
- Restituisceinteger
- il numero di cifre decimali in n
Vincoli
0 ≤ n ≤ 231-1
Esempi
- Input
- n = 4096
- Output
- 4
- Spiegazione
- La divisione intera per 10 trasforma
4096in409,40e4. Sono tre cifre rimosse e ne resta una, quindi la risposta è4.
- Input
- n = 0
- Output
- 1
- Spiegazione
0si scrive con una sola cifra. Un ciclo che conta finché il numero è maggiore di 0 qui non viene mai eseguito e restituirebbe0invece di1.
- Input
- n = 100
- Output
- 3
- Spiegazione
- Anche gli zeri sono cifre:
100si scrive1,0,0, quindi la risposta è3.
+16 test nascosti all’invio
Per approfondire
Riesci a contare le cifre senza un ciclo che venga eseguito una volta per ogni cifra, ad esempio con una ricerca binaria tra le potenze di dieci?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Che cosa succede al numero di cifre quando dividi un numero per 10 e scarti il resto?
Ogni divisione intera per 10 rimuove esattamente una cifra dalla fine. Conta quante divisioni servono per arrivare a una sola cifra.
Avvia un contatore da 1 e dividi per 10 finché il numero è almeno 10, aggiungendo 1 ogni volta. Iniziare da 1 dà anche la risposta corretta per
0.
Soluzione
Il conteggio delle cifre è il numero di volte che puoi dividere per 10 prima che rimanga una cifra, più quella cifra. L'idea sta in una riga; il lavoro è nei casi limite. 0 ha una cifra, il conteggio cambia tra 9 e 10, e una formula basata sul logaritmo non funziona con 0 e, in virgola mobile, poco prima delle grandi potenze di dieci.
Scrivi il numero come testo e conta i caratteri
Intuizione
Il tuo linguaggio sa già come scrivere n in decimale. Chiedigli quella stringa e conta i caratteri: 4096 diventa "4096", quattro caratteri. 0 diventa "0", un carattere, quindi zero non richiede casi speciali.
La conversione divide per 10 all'interno della libreria, una volta per cifra, quindi il lavoro è O(log n). La stringa contiene un carattere per cifra, ovvero O(log n) di memoria aggiuntiva, al massimo 10 caratteri qui.
La formattazione deve essere in decimale semplice. In R, as.character(1e5) restituisce "1e+05", cinque caratteri per un numero di sei cifre, quindi formatta con sprintf("%.0f", n). In Lua 5.3 e versioni successive, tostring(4096.0) mantiene il .0, mentre string.format("%d", n) scrive l'intero in ogni versione.
Algoritmo
- Converti
nin una stringa decimale con una funzione che non passa mai alla notazione scientifica. - Conta i caratteri della stringa.
- Restituisci quel conteggio. Per
0la stringa è"0", quindi la risposta è1senza controlli aggiuntivi.
def countDigits(n):
return len(str(n))Dividi per 10 finché non rimane una sola cifra
Intuizione
La divisione intera per 10 rimuove l'ultima cifra: 4096 / 10 è 409. Ogni divisione elimina una cifra, quindi il numero di divisioni necessarie per arrivare a una sola cifra, più uno per quell'ultima cifra, è la risposta. 4096 richiede tre divisioni (409, 40, 4), quindi ha 4 cifre.
Inizia il conteggio da 1 e dividi mentre n ≥ 10. Iniziare da 1 indica che ogni numero ha almeno una cifra, che è esattamente la regola per 0. La versione che si scrive per prima, contando da 0 mentre n > 0, restituisce 0 per n = 0 e richiede un controllo separato.
Il ciclo viene eseguito una volta per ogni cifra dopo la prima, al massimo 9 volte per 2147483647, quindi richiede O(log n) tempo. Mantiene un solo contatore e modifica la propria copia di n, usando O(1) spazio aggiuntivo.
Algoritmo
- Imposta
count = 1, per la cifra che è sempre presente. - Finché
n ≥ 10, dividinper 10 con la divisione intera e aggiungi 1 acount. - Quando rimane una cifra, restituisci
count.
def countDigits(n):
count = 1 # every number, 0 included, has at least one digit
while n >= 10:
n //= 10
count += 1
return count
Trappole e casi limite
Ogni bug di questo problema si trova ai margini.
- Contare da 0 mentre
n > 0. È corretto per ogni numero positivo e restituisce0pern = 0. - Usare
floor(log10(n)) + 1. Non funziona con0, per cui il logaritmo è meno infinito, e con valori grandi appena inferiori a una potenza di dieci: in doppia precisionelog10(10^15-1)viene arrotondato esattamente a15, quindi la formula indica 16 cifre invece di 15. - Divisione reale in un ciclo che continua mentre
n > 0. In JavaScript, Lua, PHP e R,/mantiene la parte frazionaria, quindi4096diminuisce avvicinandosi a 0 per 328 passaggi prima di raggiungerlo. UsaMath.floor,math.floor,intdivo%/%. - Notazione scientifica nella versione con stringhe: R scrive
100000come"1e+05". - Contare un segno meno come una cifra. Qui l'input non è mai negativo, ma
String(-42)ha tre caratteri, quindi una versione per i numeri negativi prende prima il valore assoluto.
Domande frequenti4
Come si contano le cifre di un numero senza convertirlo in una stringa?
Dividilo per 10 con la divisione intera finché non rimane una cifra, contando le divisioni, e aggiungi 1 per l’ultima cifra. 4096 diventa 409, 40, 4: tre divisioni, quindi 4 cifre. Il ciclo usa uno spazio aggiuntivo O(1).
Perché 0 ha una sola cifra?
Zero si scrive con il singolo carattere 0, quindi la sua forma decimale ha una cifra. Il codice che conta le divisioni mentre il numero è maggiore di 0 non viene mai eseguito per 0 e restituisce 0. Iniziare il contatore da 1 e dividere finché il numero è almeno 10 gestisce il caso senza eccezioni speciali.
Puoi usare log10 per contare le cifre di un numero?
Per un n positivo, il conteggio è floor(log10(n)) + 1, ma il logaritmo viene calcolato in virgola mobile. Non è definito per 0 e, vicino a una potenza di dieci, può essere arrotondato nel modo sbagliato: log10(10^15-1) risulta esattamente 15 in doppia precisione. La divisione intera dà ogni volta la risposta esatta.
Qual è la complessità temporale del conteggio delle cifre?
Un numero n ha floor(log10(n)) + 1 cifre e il ciclo esegue una divisione per ogni cifra, quindi richiede un tempo O(log n). Per un intero a 32 bit, sono al massimo 10 passaggi.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
Python
def countDigits(n):
# Scrivi il codice quiCaso 1
Caso 2
Caso 3
Input
n = 4096
Atteso
4