Count Digits

Q: Qual è la complessità temporale del conteggio delle cifre?

Un numero n ha floor(log10(n)) + 1 cifre e il ciclo esegue una divisione per cifra, quindi richiede un tempo O(log n) e uno spazio O(1) . Per un intero a 32 bit, sono al massimo 10 passaggi.

Q: 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 nella direzione sbagliata: log10(10^15-1) risulta esattamente 15 in precisione doppia. La divisione intera è sempre esatta.

PrincipianteMatematica e simulazione

+10

Dato un intero non negativo n, restituisci quante cifre ha quando è scritto in base 10 senza zeri iniziali. Lo zero si scrive come un singolo 0, quindi ha una cifra.

Funzione

countDigits(n: integer) → integer

ninteger: l'intero non negativo da misurare
Restituisceinteger: il numero di cifre decimali in n

Vincoli

0 ≤ n ≤ 2³¹-1

Esempi

Input: n = 4096
Output: 4
Spiegazione: La divisione intera per 10 trasforma 4096 in 409, 40 e 4: vengono rimosse tre cifre e ne rimane una, quindi la risposta è 4.

Input: n = 0
Output: 1
Spiegazione: 0 si scrive con una sola cifra. Un ciclo che conta finché il numero è maggiore di 0 qui non viene mai eseguito e restituisce 0 invece di 1.

Input: n = 100
Output: 3
Spiegazione: Anche gli zeri sono cifre: 100 si scrive 1, 0, 0, quindi la risposta è 3.

Per approfondire

Riesci a contare le cifre senza un ciclo che venga eseguito una volta per cifra, per esempio con una ricerca binaria sulle potenze di dieci?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Ogni divisione intera per 10 rimuove una cifra. Conta le divisioni finché non rimane una cifra, poi aggiungi uno per quella cifra. I bug si nascondono nei casi limite: 0 ha una cifra e una formula con il logaritmo non funziona con 0 e poco al di sotto delle grandi potenze di dieci.

Scrivi il numero in lettere e conta i caratteri

Intuizione

La tua lingua scrive già n in decimale. Richiedi quella stringa e contane i caratteri: 4096 diventa "4096", quattro caratteri, e 0 diventa "0", quindi zero non richiede casi speciali.

La conversione esegue una divisione per cifra, quindi sia il tempo sia la memoria aggiuntiva sono O(log n), al massimo 10 caratteri in questo caso.

Algoritmo

Converti n nella sua rappresentazione decimale come stringa con una funzione che non passa mai alla notazione scientifica.
Conta i caratteri della stringa.
Restituisci quel conteggio. Per 0 la stringa è "0", quindi la risposta è 1 senza controlli aggiuntivi.

def countDigits(n):
    return len(str(n))

Dividi per 10 finché non rimane una sola cifra

Intuizione

Inizia il conteggio da 1 e dividi per 10 finché n ≥ 10, aggiungendo 1 per ogni divisione. Iniziare da 1 indica che ogni numero ha almeno una cifra, che è esattamente la regola per 0, quindi non è necessario alcun controllo separato.

Il ciclo viene eseguito al massimo 9 volte, per 2147483647: tempo O(log n). Mantiene un solo contatore e modifica la propria copia di n, quindi lo spazio aggiuntivo è O(1).

Algoritmo

Imposta count = 1, per la cifra che è sempre presente.
Finché n ≥ 10, dividi n per 10 con la divisione intera e aggiungi 1 a count.
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

Contare da 0 mentre n > 0. Restituisce 0 per n = 0.
Usare floor(log10(n)) + 1. Non funziona con 0, dove il logaritmo è meno infinito, né con 10^15-1, dove la precisione doppia arrotonda il logaritmo esattamente a 15 e la formula indica 16 cifre.
La divisione reale in JavaScript, Lua, PHP o R, dove / conserva la parte frazionaria. Un ciclo con n > 0 viene quindi eseguito 328 volte per 4096. Usa Math.floor, math.floor, intdiv oppure %/%.
La notazione scientifica nella versione con stringhe. R scrive as.character(1e5) come "1e+05"; usa sprintf("%.0f", n). In Lua 5.3 e versioni successive, tostring(4096.0) mantiene il .0; usa string.format("%d", n).

Domande frequenti3

Qual è la complessità temporale del conteggio delle cifre?

Un numero n ha floor(log10(n)) + 1 cifre e il ciclo esegue una divisione per cifra, quindi richiede un tempo O(log n) e uno spazio O(1). Per un intero a 32 bit, sono al massimo 10 passaggi.

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 nella direzione sbagliata: log10(10^15-1) risulta esattamente 15 in precisione doppia. La divisione intera è sempre esatta.

Come si contano le cifre di un numero negativo?

Prima calcola il valore assoluto, poi conta come al solito. String(-42) ha tre caratteri perché il segno meno non è una cifra. Per il più piccolo intero a 32 bit, calcola il valore assoluto usando un tipo a 64 bit, perché non rientra in 32 bit.

def countDigits(n):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

n = 4096

Output atteso