Count Digits

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 und benötigt O(1) Speicherplatz. Bei einer 32-Bit-Ganzzahl sind das höchstens 10 Schritte.

Q: Kannst du log10 verwenden, um die Ziffern einer Zahl zu zählen?

Für ein positives n ist die Anzahl floor(log10(n)) + 1 , aber der Logarithmus wird mit Gleitkommaarithmetik 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 ist immer exakt.

EinsteigerMathe und Simulation

+10

Gegeben sei eine nicht negative ganze Zahl n. Gib zurück, wie viele Ziffern sie hat, wenn sie zur Basis 10 ohne führende Nullen geschrieben wird. Null wird als einzelne 0 geschrieben und hat daher eine Ziffer.

Funktion

countDigits(n: integer) → integer

ninteger: die nichtnegative Ganzzahl zum Messen
Gibt zurückinteger: die Anzahl der Dezimalstellen in n

Einschränkungen

0 ≤ n ≤ 2³¹-1

Beispiele

Eingabe: n = 4096
Ausgabe: 4
Erklärung: Die Ganzzahldivision durch 10 macht aus 4096 409, 40 und 4: Drei Ziffern wurden entfernt und eine blieb ü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 gibt 0 statt 1 zurück.

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

Weiterführende Frage

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

Tipps

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

0 von 3 geöffnet

Lösung

Jede ganzzahlige Division durch 10 entfernt eine Ziffer. Zähle die Divisionen, bis eine Ziffer übrig ist, und addiere dann eins für diese Ziffer. Die Fehler liegen an den Rändern: 0 hat eine Ziffer, und eine Logarithmusformel versagt bei 0 und knapp unter großen Zehnerpotenzen.

Schreibe die Zahl als Text und zähle die Zeichen

Idee

Deine Sprache schreibt n bereits dezimal. Frage nach dieser Zeichenfolge und zähle ihre Zeichen: Aus 4096 wird "4096", also vier Zeichen, und aus 0 wird "0", daher ist für null kein Sonderfall nötig.

Die Umwandlung führt eine Division pro Ziffer aus, daher betragen sowohl die Laufzeit als auch der zusätzliche Speicherbedarf O(log n), hier höchstens 10 Zeichen.

Algorithmus

Wandle n mit einer Funktion, die nie 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 und es ist keine zusätzliche Prüfung erforderlich.

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

So lange durch 10 teilen, bis eine Ziffer übrig ist

Idee

Beginne die Zählung bei 1 und teile durch 10, solange n ≥ 10, wobei du pro Division 1 addierst. Bei 1 zu beginnen bedeutet, dass jede Zahl mindestens eine Ziffer hat. Das ist genau die Regel für 0, daher ist keine separate Prüfung erforderlich.

Die Schleife wird höchstens 9-mal ausgeführt, bei 2147483647: Laufzeit O(log n). Sie verwendet einen Zähler und ändert ihre eigene Kopie von n, daher beträgt der zusätzliche Speicherbedarf 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 ist, 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

Zählen ab 0, solange n > 0 gilt. Für n = 0 wird 0 zurückgegeben.
Verwendung von floor(log10(n)) + 1. Bei 0 schlägt es fehl, da der Logarithmus minus unendlich ist, und bei 10^15-1, da die doppelte Genauigkeit den Logarithmus auf exakt 15 rundet und die Formel 16 Ziffern ergibt.
Reelle Division in JavaScript, Lua, PHP oder R, bei der / den Bruchteil beibehält. Eine Schleife, die läuft, solange n > 0 gilt, wird dann für 4096 328-mal ausgeführt. Verwende Math.floor, math.floor, intdiv oder %/%.
Wissenschaftliche Schreibweise in der String-Version. R gibt as.character(1e5) als "1e+05" aus; verwende sprintf("%.0f", n). In Lua 5.3 und später behält tostring(4096.0) die .0 bei; verwende string.format("%d", n).

Häufige Fragen3

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 und benötigt O(1) Speicherplatz. Bei einer 32-Bit-Ganzzahl sind das höchstens 10 Schritte.

Kannst du log10 verwenden, um die Ziffern einer Zahl zu zählen?

Für ein positives n ist die Anzahl floor(log10(n)) + 1, aber der Logarithmus wird mit Gleitkommaarithmetik 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 ist immer exakt.

Wie zählt man die Ziffern einer negativen Zahl?

Bestimme zuerst den Absolutwert und zähle dann wie gewohnt. String(-42) hat drei Zeichen, da das Minuszeichen keine Ziffer ist. Für die kleinste 32-Bit-Ganzzahl solltest du den Absolutwert in einem 64-Bit-Typ bestimmen, da sie nicht in 32 Bit passt.

def countDigits(n):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

n = 4096

Erwartete Ausgabe