Count Digits
Napisz funkcję, która przyjmuje nieujemną liczbę całkowitą n i zwraca liczbę jej cyfr w zapisie dziesiętnym bez zer wiodących. Zero zapisuje się jako pojedyncze 0, więc ma jedną cyfrę.
Funkcja
- ninteger
- nieujemna liczba całkowita do zmierzenia
- Zwracainteger
- liczba cyfr dziesiętnych w n
Ograniczenia
0 ≤ n ≤ 231-1
Przykłady
- Wejście
- n = 4096
- Wyjście
- 4
- Wyjaśnienie
- Dzielenie całkowite przez 10 przekształca
4096w409,40i4. To trzy usunięte cyfry i jedna pozostała, więc odpowiedź to4.
- Wejście
- n = 0
- Wyjście
- 1
- Wyjaśnienie
0zapisuje się za pomocą jednej cyfry. Pętla, która liczy, dopóki liczba jest większa od 0, w tym przypadku nigdy się nie wykona i zwróci0zamiast1.
- Wejście
- n = 100
- Wyjście
- 3
- Wyjaśnienie
- Zera również są cyframi:
100zapisuje się jako1,0,0, więc odpowiedź to3.
+16 ukrytych testów przy wysłaniu
Pytanie dodatkowe
Czy potrafisz policzyć cyfry bez używania pętli, która wykonuje się raz dla każdej cyfry, 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.
Co dzieje się z liczbą cyfr, gdy podzielisz liczbę przez 10 i odrzucisz resztę?
Każde dzielenie całkowite przez 10 usuwa dokładnie jedną cyfrę z końca. Policz, ile dzieleń potrzeba, aby otrzymać jedną cyfrę.
Rozpocznij licznik od 1 i dziel przez 10, dopóki liczba jest większa lub równa 10, za każdym razem dodając 1. Rozpoczęcie od 1 daje również prawidłowy wynik dla
0.
Rozwiązanie
Liczba cyfr to liczba razy, ile można podzielić przez 10, zanim zostanie jedna cyfra, plus ta cyfra. Pomysł mieści się w jednym wierszu; trudności tkwią w przypadkach brzegowych. 0 ma jedną cyfrę, liczba cyfr zmienia się między 9 a 10, a wzór oparty na logarytmie nie działa dla 0 i, przy arytmetyce zmiennoprzecinkowej, nieco poniżej dużych potęg dziesięciu.
Zapisz liczbę słownie i policz znaki
Intuicja
Twój język już wie, jak zapisać n w systemie dziesiętnym. Poproś go o ten ciąg znaków i policz znaki: 4096 staje się "4096" — to cztery znaki. 0 staje się "0" — to jeden znak, więc zero nie wymaga osobnego przypadku.
Konwersja dzieli przez 10 wewnątrz biblioteki, raz na każdą cyfrę, więc jej złożoność wynosi O(log n). Ciąg znaków zawiera po jednym znaku na każdą cyfrę, co oznacza dodatkową pamięć O(log n) — tutaj najwyżej 10 znaków.
Formatowanie musi używać zwykłego zapisu dziesiętnego. W R as.character(1e5) zwraca "1e+05" — pięć znaków dla liczby sześciocyfrowej, więc formatuj za pomocą sprintf("%.0f", n). W Lua 5.3 i nowszych tostring(4096.0) zachowuje .0, a string.format("%d", n) zapisuje liczbę całkowitą w każdej wersji.
Algorytm
- Przekształć
nna zapis dziesiętny w postaci ciągu znaków za pomocą funkcji, która nigdy nie przechodzi na notację naukową. - Policz znaki w ciągu.
- Zwróć tę liczbę. Dla
0ciąg to"0", więc odpowiedzią jest1bez dodatkowego sprawdzania.
def countDigits(n):
return len(str(n))Dzielenie przez 10, aż zostanie jedna cyfra
Intuicja
Dzielenie całkowite przez 10 usuwa ostatnią cyfrę: 4096 / 10 to 409. Każde dzielenie usuwa jedną cyfrę, więc odpowiedzią jest liczba dzieleń potrzebnych do uzyskania jednej cyfry, powiększona o jeden za tę ostatnią cyfrę. W przypadku 4096 potrzeba trzech dzieleń (409, 40, 4), więc liczba ta ma 4 cyfry.
Rozpocznij liczenie od 1 i dziel, dopóki n ≥ 10. Rozpoczęcie od 1 oznacza, że każda liczba ma co najmniej jedną cyfrę, co dokładnie odpowiada zasadzie dla 0. Wersja, którą ludzie zapisują jako pierwszą — liczenie od 0, dopóki n > 0 — zwraca 0 dla n = 0 i wymaga osobnego sprawdzenia.
Pętla wykonuje się raz dla każdej cyfry po pierwszej, najwyżej 9 razy dla 2147483647, więc jej czas działania wynosi O(log n). Przechowuje jeden licznik i zmienia własną kopię n, co wymaga dodatkowego miejsca O(1).
Algorytm
- Ustaw
count = 1dla cyfry, która jest zawsze obecna. - Dopóki
n ≥ 10, dzielnprzez 10 z użyciem dzielenia całkowitego i dodawaj 1 docount. - 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
Każdy błąd w tym zadaniu znajduje się na granicy.
- Liczenie od 0, gdy
n > 0. To działa dla każdej liczby dodatniej i zwraca0dlan = 0. - Użycie
floor(log10(n)) + 1. Nie działa dla0, dla którego logarytm wynosi minus nieskończoność, ani dla dużych wartości nieco mniejszych od potęgi dziesięciu: w podwójnej precyzjilog10(10^15-1)zaokrągla się dokładnie do15, więc wzór podaje 16 cyfr zamiast 15. - Dzielenie rzeczywiste w pętli, która działa, dopóki
n > 0. W JavaScript, Lua, PHP i R operator/zachowuje część ułamkową, więc4096zbliża się do 0 przez 328 kroków, zanim do niego dotrze. UżyjMath.floor,math.floor,intdivlub%/%. - Zapis naukowy w wersji łańcuchowej: R zapisuje
100000jako"1e+05". - Znak minus policzony jako cyfra. Dane wejściowe nigdy nie są tu ujemne, ale
String(-42)ma trzy znaki, więc wersja obsługująca liczby ujemne najpierw bierze wartość bezwzględną.
Najczęstsze pytania4
Jak policzyć cyfry liczby bez zamieniania jej na ciąg znaków?
Dziel przez 10, używając dzielenia całkowitego, aż pozostanie jedna cyfra. Zliczaj dzielenia i dodaj 1 za ostatnią cyfrę. 4096 staje się 409, 40, 4: trzy dzielenia, czyli 4 cyfry. Pętla wykorzystuje dodatkową pamięć O(1).
Dlaczego 0 ma jedną cyfrę?
Zero zapisuje się jako pojedynczy znak 0, więc jego zapis dziesiętny ma jedną cyfrę. Kod, który zlicza dzielenia, gdy liczba jest większa od 0, nigdy nie uruchamia się dla 0 i zwraca 0. Rozpoczęcie licznika od 1 i dzielenie, gdy liczba jest większa lub równa 10, obsługuje ten przypadek bez specjalnego wyjątku.
Czy możesz użyć log10, aby policzyć cyfry liczby?
Dla dodatniego n liczba 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 zaokrąglić w niewłaściwą stronę: log10(10^15-1) daje dokładnie 15 w podwójnej precyzji. Dzielenie całkowitoliczbowe zawsze daje dokładny wynik.
Jaka jest złożoność czasowa liczenia 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). W przypadku liczby całkowitej 32-bitowej zajmuje to najwyżej 10 kroków.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
Python
def countDigits(n):
# Napisz kod tutajPrzypadek 1
Przypadek 2
Przypadek 3
Wejście
n = 4096
Oczekiwane
4