Count Digits

Q: Warum hat 0 eine Ziffer?

Null wird als einzelnes Zeichen 0 geschrieben, daher hat seine Dezimaldarstellung eine Ziffer. Code, der Divisionen zählt, solange die Zahl größer als 0 ist, wird für 0 nie ausgeführt und gibt 0 zurück. Wenn man den Zähler bei 1 beginnen lässt und so lange dividiert, wie die Zahl mindestens 10 beträgt, wird der Fall ohne Sonderbehandlung abgedeckt.

Q: Kannst du mit log10 die Ziffern einer Zahl zählen?

Für ein positives n ist die Anzahl floor(log10(n)) + 1 , aber der Logarithmus wird mit Gleitkommazahlen berechnet. Für 0 ist er undefiniert, und nahe einer Zehnerpotenz kann er falsch gerundet werden: log10(10^15-1) ergibt in doppelter Genauigkeit genau 15. Ganzzahldivision liefert jedes Mal die exakte Antwort.

Q: Wie hoch ist die Zeitkomplexität beim Zählen von Ziffern?

Eine Zahl n hat floor(log10(n)) + 1 Ziffern, und die Schleife führt pro Ziffer eine Division aus, daher läuft sie in O(log n) -Zeit. Bei einer 32-Bit-Ganzzahl sind das höchstens 10 Schritte.

EinsteigerMathe und Simulation

+10

Schreibe eine Funktion, die eine nichtnegative ganze Zahl n erhält und zurückgibt, wie viele Ziffern sie hat, wenn du sie im Zehnersystem ohne führende Nullen schreibst. Null wird als einzelne 0 geschrieben und hat daher eine Ziffer.

Funktion

countDigits(n: integer) → integer

ninteger: die nichtnegative ganze Zahl, die gemessen werden soll
Gibt zurückinteger: die Anzahl der Dezimalstellen in n

Einschränkungen

0 ≤ n ≤ 2³¹-1

Beispiele

Eingabe: n = 4096
Ausgabe: 4
Erklärung: Ganzzahldivision durch 10 macht aus 4096 409, 40 und 4. Dabei werden drei Ziffern entfernt und eine bleibt übrig, also lautet die Antwort 4.

Eingabe: n = 0
Ausgabe: 1
Erklärung: 0 wird mit einer Ziffer geschrieben. Eine Schleife, die zählt, solange die Zahl größer als 0 ist, wird hier nie ausgeführt und würde statt 1 den Wert 0 zurückgeben.

Eingabe: n = 100
Ausgabe: 3
Erklärung: Die Nullen sind ebenfalls Ziffern: 100 wird als 1, 0, 0 geschrieben, also lautet die Antwort 3.

+16 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du die Ziffern zählen, ohne eine Schleife zu verwenden, die einmal pro Ziffer ausgeführt wird, zum Beispiel mit einer binären Suche über die Zehnerpotenzen?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Die Ziffernanzahl ist die Anzahl der Male, die du durch 10 teilen kannst, bevor nur noch eine Ziffer übrig bleibt, plus diese Ziffer. Die Idee passt in eine Zeile; die Arbeit steckt in den Randfällen. 0 hat eine Ziffer, die Anzahl ändert sich zwischen 9 und 10, und eine auf einem Logarithmus basierende Formel scheitert bei 0 und bei Gleitkommazahlen ein wenig unterhalb großer Zehnerpotenzen.

Schreibe die Zahl als Text und zähle die Zeichen

Idee

Deine Sprache weiß bereits, wie sie n dezimal schreibt. Lass sie diesen String zurückgeben und zähle die Zeichen: Aus 4096 wird "4096", also vier Zeichen. Aus 0 wird "0", also ein Zeichen; null braucht daher keinen Sonderfall.

Die Umwandlung dividiert innerhalb der Bibliothek einmal pro Ziffer durch 10, daher beträgt der Aufwand O(log n). Der String enthält ein Zeichen pro Ziffer, was O(log n) zusätzlichen Speicherplatz bedeutet, hier höchstens 10 Zeichen.

Die Formatierung muss dezimal ohne Exponentialschreibweise sein. In R ergibt as.character(1e5) den Wert "1e+05", fünf Zeichen für eine sechsstellige Zahl; formatiere daher mit sprintf("%.0f", n). In Lua 5.3 und später behält tostring(4096.0) die .0 bei, während string.format("%d", n) die Ganzzahl in jeder Version ausgibt.

Algorithmus

Wandle n mit einer Funktion, die niemals zur wissenschaftlichen Notation wechselt, in eine Dezimalzeichenfolge um.
Zähle die Zeichen der Zeichenfolge.
Gib diese Anzahl zurück. Für 0 lautet die Zeichenfolge "0", daher ist die Antwort 1 – ohne zusätzliche Prüfung.

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

Teile durch 10, bis eine Ziffer übrig bleibt

Idee

Die Ganzzahldivision durch 10 entfernt die letzte Ziffer: 4096 / 10 ist 409. Jede Division entfernt eine Ziffer. Die Anzahl der Divisionen, die nötig sind, um eine einzelne Ziffer zu erreichen, plus eins für diese letzte Ziffer, ist also die Antwort. Für 4096 sind drei Divisionen erforderlich (409, 40, 4), es hat also 4 Ziffern.

Beginne die Zählung bei 1 und dividiere, solange n ≥ 10 gilt. Der Start bei 1 bedeutet, dass jede Zahl mindestens eine Ziffer hat – genau das gilt auch für 0. Die Variante, mit der viele zuerst beginnen – von 0 aus zählen, solange n > 0 gilt –, gibt für n = 0 den Wert 0 zurück und erfordert eine separate Prüfung.

Die Schleife läuft für jede Ziffer nach der ersten einmal, für 2147483647 also höchstens 9-mal. Daher benötigt sie O(log n) Zeit. Sie verwendet einen Zähler und verändert ihre eigene Kopie von n; der zusätzliche Speicherbedarf beträgt somit O(1).

Algorithmus

Setze count = 1 für die Ziffer, die immer vorhanden ist.
Solange n ≥ 10 gilt, teile n mit ganzzahliger Division durch 10 und addiere 1 zu count.
Wenn eine Ziffer übrig bleibt, gib count zurück.

def countDigits(n):
    count = 1  # every number, 0 included, has at least one digit
    while n >= 10:
        n //= 10
        count += 1
    return count

Stolperfallen und Grenzfälle

Jeder Fehler in diesem Problem tritt an einem Randfall auf.

Bei n > 0 ab 0 zählen. Das ist für jede positive Zahl korrekt und gibt für n = 0 den Wert 0 zurück.
floor(log10(n)) + 1 verwenden. Das schlägt bei 0 fehl, wo der Logarithmus minus unendlich ist, und bei großen Werten knapp unter einer Zehnerpotenz: Bei doppelter Genauigkeit wird log10(10^15-1) auf genau 15 gerundet, sodass die Formel 16 statt 15 Ziffern ergibt.
Reelle Division in einer Schleife verwenden, die läuft, solange n > 0. In JavaScript, Lua, PHP und R behält / den Nachkommaanteil bei, sodass 4096 in 328 Schritten gegen 0 schrumpft, bevor es diesen Wert erreicht. Verwende Math.floor, math.floor, intdiv oder %/%.
Wissenschaftliche Schreibweise in der String-Version: R schreibt 100000 als "1e+05".
Ein Minuszeichen als Ziffer zählen. Die Eingabe ist hier nie negativ, aber String(-42) hat drei Zeichen, daher nimmt eine Version für negative Zahlen zuerst den Absolutwert.

Häufige Fragen4

Wie zählt man die Ziffern einer Zahl, ohne sie in eine Zeichenkette umzuwandeln?

Teile es mit ganzzahliger Division durch 10, bis eine Ziffer übrig ist, zähle die Divisionen und addiere 1 für die letzte Ziffer. 4096 wird zu 409, 40, 4: drei Divisionen, also 4 Ziffern. Die Schleife benötigt zusätzlich O(1) Speicherplatz.

Warum hat 0 eine Ziffer?

Null wird als einzelnes Zeichen 0 geschrieben, daher hat seine Dezimaldarstellung eine Ziffer. Code, der Divisionen zählt, solange die Zahl größer als 0 ist, wird für 0 nie ausgeführt und gibt 0 zurück. Wenn man den Zähler bei 1 beginnen lässt und so lange dividiert, wie die Zahl mindestens 10 beträgt, wird der Fall ohne Sonderbehandlung abgedeckt.

Kannst du mit log10 die Ziffern einer Zahl zählen?

Für ein positives n ist die Anzahl floor(log10(n)) + 1, aber der Logarithmus wird mit Gleitkommazahlen berechnet. Für 0 ist er undefiniert, und nahe einer Zehnerpotenz kann er falsch gerundet werden: log10(10^15-1) ergibt in doppelter Genauigkeit genau 15. Ganzzahldivision liefert jedes Mal die exakte Antwort.

Wie hoch ist die Zeitkomplexität beim Zählen von Ziffern?

Eine Zahl n hat floor(log10(n)) + 1 Ziffern, und die Schleife führt pro Ziffer eine Division aus, daher läuft sie in O(log n)-Zeit. Bei einer 32-Bit-Ganzzahl sind das höchstens 10 Schritte.

Python

def countDigits(n):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

n = 4096

Erwartet