Sum of Digits

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

Jeden krok na każdą cyfrę, czyli O(d) , gdzie d to liczba cyfr. Liczba n ma około log10(n) + 1 cyfr, więc tę samą granicę często zapisuje się jako O(log n) . Dla liczby całkowitej 32-bitowej to najwyżej 10 kroków.

Q: Jak uzyskać cyfry liczby bez konwertowania jej na ciąg znaków?

Użyj reszty z dzielenia i dzielenia całkowitego przez 10. n % 10 to ostatnia cyfra, a dzielenie n przez 10 z odrzuceniem reszty usuwa tę cyfrę. Powtarzaj, aż n osiągnie 0, a odwiedzisz każdą cyfrę od prawej do lewej.

Q: Czy lepsza jest wersja tekstowa czy arytmetyczna?

Oba rozwiązania mają złożoność O(d) i oba są poprawne. Wersję z użyciem ciągu znaków łatwiej zapisać w wielu językach, ale tworzy ona kopię cyfr. Wersja arytmetyczna używa dodatkowej pamięci O(1) i pokazuje osobie przeprowadzającej rozmowę kwalifikacyjną, że wiesz, jak operatory % 10 i / 10 rozkładają liczbę na części — to przydaje się w zadaniach dotyczących palindromów i odwracania cyfr.

PoczątkującyMatematyka i symulacja

+10

Otrzymujesz nieujemną liczbę całkowitą n. Zwróć sumę jej cyfr dziesiętnych. Na przykład cyfry liczby 482 to 4, 8 i 2, więc odpowiedzią jest 14.

Funkcja

sumOfDigits(n: integer) → integer

ninteger: nieujemna liczba całkowita, której cyfry dodajesz
Zwracainteger: suma cyfr dziesiętnych liczby n

Ograniczenia

0 ≤ n ≤ 2³¹-1

Przykłady

Wejście: n = 9045
Wyjście: 18
Wyjaśnienie: Cyfry liczby 9045 to 9, 0, 4 i 5, a 9 + 0 + 4 + 5 = 18. Zero niczego nie dodaje, ale nadal jest cyfrą.

Wejście: n = 7
Wyjście: 7
Wyjaśnienie: Liczba jednocyfrowa jest równa sumie swoich cyfr, więc 7 daje 7.

+15 ukrytych testów przy wysłaniu

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Liczba nie podaje swoich cyfr pojedynczo — musisz ją rozłożyć. Możesz zamienić ją na tekst i odczytać znaki albo użyć dwóch działań arytmetycznych, które odrywają ostatnią cyfrę: n % 10 ją zwraca, a dzielenie całkowite przez 10 ją usuwa. Obie metody wymagają jednego kroku na każdą cyfrę, oznaczoną poniżej jako d, przy czym tutaj d ≤ 10. Wersja arytmetyczna nie wymaga dodatkowej pamięci.

Odczytaj cyfry jako tekst

Intuicja

Gdy zapisujesz liczbę, od razu widzisz jej cyfry. Zamień n na jej zapis dziesiętny: 9045 staje się czterema znakami: 9, 0, 4 i 5. Następnie przejdź po znakach i dodaj wartość każdego z nich.

Znak nie jest jeszcze liczbą. Znak '4' jest przechowywany jako kod 52, więc zamień go na liczbę lub odejmij kod znaku '0': '4' - '0' = 4. Kody znaków cyfr występują kolejno po sobie, dlatego to odejmowanie działa dla wszystkich dziesięciu cyfr.

Tekst ma d znaków, po jednym na każdą cyfrę, więc pętla działa w czasie O(d), a sam tekst zajmuje dodatkowe O(d) miejsca.

Algorytm

Przekonwertuj n na jego zapis dziesiętny.
Ustaw total = 0.
Dla każdego znaku dodaj jego wartość cyfry do total.
Zwróć total.

def sumOfDigits(n):
    total = 0
    for digit in str(n):
        total += int(digit)
    return total

Usuń ostatnią cyfrę za pomocą % 10

Intuicja

Możesz rozłożyć liczbę na części bez użycia tekstu. Reszta z dzielenia przez 10 to ostatnia cyfra: 9045 % 10 = 5. Dzielenie całkowite przez 10 odrzuca tę cyfrę: 9045 / 10 = 904, gdy pominiemy część ułamkową. Powtarzaj tę parę działań, a cyfry będą pojawiać się od prawej do lewej.

Dla 9045: dodaj 5 i zachowaj 904, dodaj 4 i zachowaj 90, dodaj 0 i zachowaj 9, dodaj 9 i zachowaj 0. Pętla kończy się przy 0, a suma wynosi 18. Dla n = 0 pętla w ogóle się nie uruchamia, a wynik to 0, co jest poprawne.

Każdy krok usuwa jedną cyfrę, więc mamy d kroków, czas O(d), a w pamięci znajdują się tylko dwie liczby całkowite, co oznacza O(1) pamięci. Każda wartość pośrednia jest mniejsza niż n, więc nie może dojść do przepełnienia.

Algorytm

Ustaw total = 0.
Gdy n > 0, dodaj n % 10 do total.
Podziel n przez 10, odrzucając część ułamkową.
Gdy n osiągnie 0, zwróć total.

def sumOfDigits(n):
    total = 0
    while n > 0:
        total += n % 10  # last digit
        n //= 10         # drop the last digit
    return total

Pułapki i przypadki brzegowe

Pętla jest krótka, a błędy dotyczą typów i najmniejszego wejścia.

Używanie /, gdy w danym języku oznacza dzielenie rzeczywiste. W JavaScript, TypeScript, Lua, PHP i R 9045 / 10 to 904.5, więc pętla dodaje potem ułamki. Zaokrąglaj w dół za pomocą Math.floor lub math.floor; w Pythonie użyj //, w Dart ~/, w PHP intdiv, a w R %/%.
Dodawanie znaków zamiast cyfr. Znak '7' ma kod 55, a nie 7. Odejmij '0' lub najpierw sparsuj znak.
Zapętlanie, gdy n >= 10. Pętla zatrzymuje się wtedy, gdy w n nadal znajduje się pierwsza cyfra, i nigdy jej nie dodaje, więc dla 9045 daje 9 zamiast 18. Zapętlaj, gdy n > 0; zwróci to również 0 dla n = 0.
Wyświetlanie dużych liczb jako tekstu w R. as.character(100000) daje "1e+05", a nie sześć cyfr tej liczby. Użyj format(n, scientific = FALSE).

Najczęstsze pytania4

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

Jeden krok na każdą cyfrę, czyli O(d), gdzie d to liczba cyfr. Liczba n ma około log10(n) + 1 cyfr, więc tę samą granicę często zapisuje się jako O(log n). Dla liczby całkowitej 32-bitowej to najwyżej 10 kroków.

Jak uzyskać cyfry liczby bez konwertowania jej na ciąg znaków?

Użyj reszty z dzielenia i dzielenia całkowitego przez 10. n % 10 to ostatnia cyfra, a dzielenie n przez 10 z odrzuceniem reszty usuwa tę cyfrę. Powtarzaj, aż n osiągnie 0, a odwiedzisz każdą cyfrę od prawej do lewej.

Jaki jest pierwiastek cyfrowy liczby?

To, co otrzymujesz, sumując cyfry wielokrotnie, aż zostanie jedna cyfra: 9045 daje 18, a następnie 9. Dla dodatniego n jest równe 1 + (n-1) % 9, ponieważ każda liczba daje taką samą resztę z dzielenia przez 9 co suma jej cyfr.

Czy lepsza jest wersja tekstowa czy arytmetyczna?

Oba rozwiązania mają złożoność O(d) i oba są poprawne. Wersję z użyciem ciągu znaków łatwiej zapisać w wielu językach, ale tworzy ona kopię cyfr. Wersja arytmetyczna używa dodatkowej pamięci O(1) i pokazuje osobie przeprowadzającej rozmowę kwalifikacyjną, że wiesz, jak operatory % 10 i / 10 rozkładają liczbę na części — to przydaje się w zadaniach dotyczących palindromów i odwracania cyfr.

Python

def sumOfDigits(n):
    # Wpisz tutaj kod

Przypadki testowe

Przypadek 1

Przypadek 2

Wejście

n = 9045

Oczekiwane