Count Digits

Q: Jaka jest złożoność czasowa zliczania cyfr?

Liczba n ma floor(log10(n)) + 1 cyfr, a pętla wykonuje jedno dzielenie na każdą cyfrę, więc działa w czasie O(log n) i zajmuje O(1) miejsca. W przypadku 32-bitowej liczby całkowitej jest to najwyżej 10 kroków.

Q: Czy możesz użyć log10, aby policzyć cyfry liczby?

Dla dodatniego n liczba cyfr wynosi floor(log10(n)) + 1 , ale logarytm jest obliczany w arytmetyce zmiennoprzecinkowej. Dla 0 jest niezdefiniowany, a w pobliżu potęgi dziesięciu może zostać zaokrąglony w niewłaściwą stronę: log10(10^15-1) daje dokładnie 15 w arytmetyce podwójnej precyzji. Dzielenie całkowite jest zawsze dokładne.

Q: Jak policzyć cyfry liczby ujemnej?

Najpierw weź wartość bezwzględną, a potem licz jak zwykle. String(-42) ma trzy znaki, ponieważ znak minus nie jest cyfrą. W przypadku najmniejszej 32-bitowej liczby całkowitej weź wartość bezwzględną w typie 64-bitowym, ponieważ nie mieści się ona w 32 bitach.

PoczątkującyMatematyka i symulacja

+10

Dla danej nieujemnej liczby całkowitej n zwróć liczbę jej cyfr w zapisie dziesiętnym bez zer wiodących. Zero zapisuje się jako pojedyncze 0, więc ma jedną cyfrę.

Funkcja

countDigits(n: integer) → integer

ninteger: nieujemna liczba całkowita do zmierzenia
Zwracainteger: liczba cyfr dziesiętnych w n

Ograniczenia

0 ≤ n ≤ 2³¹-1

Przykłady

Wejście: n = 4096
Wyjście: 4
Wyjaśnienie: Dzielenie całkowite przez 10 zmienia 4096 w 409, 40 i 4: usuwa trzy cyfry, zostawiając jedną, więc odpowiedzią jest 4.

Wejście: n = 0
Wyjście: 1
Wyjaśnienie: 0 zapisuje się jedną cyfrą. Pętla, która zlicza, gdy liczba jest większa od 0, nigdy się tu nie uruchamia i zwraca 0 zamiast 1.

Wejście: n = 100
Wyjście: 3
Wyjaśnienie: Zera też są cyframi: 100 zapisuje się jako 1, 0, 0, więc odpowiedź to 3.

Pytanie dodatkowe

Czy potrafisz policzyć cyfry bez używania pętli, która wykonuje się raz na każdą cyfrę, na przykład za pomocą wyszukiwania binarnego wśród potęg dziesięciu?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Każde dzielenie całkowite przez 10 usuwa jedną cyfrę. Zliczaj dzielenia, aż zostanie jedna cyfra, a następnie dodaj jeden za tę cyfrę. Błędy kryją się na krańcach: 0 ma jedną cyfrę, a wzór z logarytmem zawodzi dla 0 i dla liczb nieco mniejszych od dużych potęg dziesięciu.

Napisz liczbę słownie i policz znaki

Intuicja

Twój język zapisuje już n w systemie dziesiętnym. Poproś o ten ciąg i policz jego znaki: 4096 staje się "4096", czyli czterema znakami, a 0 staje się "0", więc zero nie wymaga specjalnego przypadku.

Konwersja wykonuje jedno dzielenie na każdą cyfrę, więc zarówno czas, jak i dodatkowa pamięć wynoszą O(log n), tutaj najwyżej 10 znaków.

Algorytm

Przekonwertuj n na łańcuch znaków w zapisie dziesiętnym za pomocą funkcji, która nigdy nie przełącza się na notację naukową.
Policz znaki w łańcuchu.
Zwróć tę liczbę. Dla 0 łańcuch to "0", więc odpowiedzią jest 1 i nie trzeba wykonywać dodatkowego sprawdzenia.

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

Dzielenie przez 10, aż zostanie jedna cyfra

Intuicja

Rozpocznij liczenie od 1 i dziel przez 10, dopóki n ≥ 10, dodając 1 po każdym dzieleniu. Rozpoczęcie od 1 oznacza, że każda liczba ma co najmniej jedną cyfrę, co jest dokładnie regułą dla 0, więc nie jest potrzebne osobne sprawdzenie.

Pętla wykonuje się najwyżej 9 razy dla 2147483647: czas O(log n). Przechowuje jeden licznik i zmienia własną kopię n, więc dodatkowa pamięć wynosi O(1).

Algorytm

Ustaw count = 1 dla cyfry, która zawsze tam jest.
Dopóki n ≥ 10, dziel n przez 10, używając dzielenia całkowitego, i dodaj 1 do count.
Gdy zostanie jedna cyfra, zwróć count.

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

Pułapki i przypadki brzegowe

Zliczanie od 0, dopóki n > 0. Zwraca 0 dla n = 0.
Użycie floor(log10(n)) + 1. Nie działa dla 0, gdzie logarytm wynosi minus nieskończoność, ani dla 10^15-1, gdzie podwójna precyzja zaokrągla logarytm dokładnie do 15, a wzór podaje 16 cyfr.
Dzielenie rzeczywiste w JavaScript, Lua, PHP lub R, gdzie / zachowuje część ułamkową. Pętla działająca, dopóki n > 0, wykona się wtedy 328 razy dla 4096. Użyj Math.floor, math.floor, intdiv lub %/%.
Zapis naukowy w wersji łańcuchowej. R zapisuje as.character(1e5) jako "1e+05"; użyj sprintf("%.0f", n). W Lua 5.3 i nowszych tostring(4096.0) zachowuje końcówkę .0; użyj string.format("%d", n).

Najczęstsze pytania3

Jaka jest złożoność czasowa zliczania cyfr?

Liczba n ma floor(log10(n)) + 1 cyfr, a pętla wykonuje jedno dzielenie na każdą cyfrę, więc działa w czasie O(log n) i zajmuje O(1) miejsca. W przypadku 32-bitowej liczby całkowitej jest to najwyżej 10 kroków.

Czy możesz użyć log10, aby policzyć cyfry liczby?

Dla dodatniego n liczba cyfr wynosi floor(log10(n)) + 1, ale logarytm jest obliczany w arytmetyce zmiennoprzecinkowej. Dla 0 jest niezdefiniowany, a w pobliżu potęgi dziesięciu może zostać zaokrąglony w niewłaściwą stronę: log10(10^15-1) daje dokładnie 15 w arytmetyce podwójnej precyzji. Dzielenie całkowite jest zawsze dokładne.

Jak policzyć cyfry liczby ujemnej?

Najpierw weź wartość bezwzględną, a potem licz jak zwykle. String(-42) ma trzy znaki, ponieważ znak minus nie jest cyfrą. W przypadku najmniejszej 32-bitowej liczby całkowitej weź wartość bezwzględną w typie 64-bitowym, ponieważ nie mieści się ona w 32 bitach.

def countDigits(n):
    # Wpisz tutaj kod

Test #1

Test #2

Test #3

Argument

n = 4096

Oczekiwany wynik