Happy Number

Q: Dlaczego proces zawsze dochodzi do 1 lub pętli?

Liczba mająca d cyfr jest mapowana na wartość nie większą niż 81 × d , więc duże liczby szybko maleją: każda liczba początkowa nie większa niż 2^31-1 po jednym kroku spada poniżej 1000, a liczba mniejsza niż 1000 jest mapowana na wartość nie większą niż 243. Przebieg jest ograniczony do mniej niż 1000 wartości, więc musi powtórzyć jedną z nich, a od tego momentu cyklicznie się powtarza. 1 jest jedyną liczbą, która jest mapowana na samą siebie.

Q: Jaka jest złożoność czasowa algorytmu sprawdzającego szczęśliwą liczbę?

Pierwszy krok odczytuje O(log n) cyfr liczby n . Każda kolejna wartość jest mniejsza niż 1000, a przebieg powtarza się w ciągu co najwyżej 20 liczb, więc całkowity czas wynosi O(log n) . Wersja z tablicą mieszającą przechowuje odwiedzone liczby; wersja Floyda używa O(1) miejsca.

ŁatweSzybki i wolny wskaźnik Haszowanie

+10

Zacznij od dodatniej liczby całkowitej n i wielokrotnie zastępuj ją sumą kwadratów jej cyfr. Na przykład 12 staje się 1² + 2² = 5. Jeśli w tym procesie otrzymasz 1, n jest szczęśliwą liczbą; w przeciwnym razie liczby będą krążyć w nieskończoność, nigdy nie obejmując 1. Zwróć true, jeśli n jest szczęśliwą liczbą, a false, jeśli nie jest.

Funkcja

isHappy(n: integer) → boolean

ninteger: liczba całkowita dodatnia do sprawdzenia
Zwracaboolean: true, jeśli powtarzanie sumowania kwadratów cyfr prowadzi do 1, false, jeśli powtarza się w nieskończoność

Ograniczenia

1 ≤ n ≤ 2³¹-1

Przykłady

Wejście: n = 7
Wyjście: true
Wyjaśnienie: 7 staje się 49, potem 4² + 9² = 97, następnie 130, potem 10, a na końcu 1. Proces osiąga 1, więc 7 jest szczęśliwa.

Wejście: n = 2
Wyjście: false
Wyjaśnienie: 2 zmienia się w 4, 16, 37, 58, 89, 145, 42, 20, a potem znów w 4. Od tego momentu te same osiem liczb powtarza się w nieskończoność i nigdy nie osiąga 1.

Wejście: n = 100
Wyjście: true
Wyjaśnienie: 1² + 0² + 0² = 1, więc 100 osiąga 1 po jednym kroku.

+16 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Jak szybko policzyć liczby szczęśliwe od 1 do 10^6, ponownie wykorzystując wyniki dla liczb mniejszych niż 1000, zamiast za każdym razem zaczynać od początku?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Wędrówka nigdy nie może uciec do nieskończoności. Liczba 10-cyfrowa daje co najwyżej 10 × 81 = 810, a liczba mniejsza niż 1000 daje co najwyżej 3 × 81 = 243, więc po jednym kroku wędrówka pozostaje wśród mniej niż 1000 wartości i musi osiągnąć 1 lub powtórzyć liczbę. To zamienia problem w wykrywanie cykli: zapamiętuj, co już widziałeś, albo uruchom powolnego i szybkiego wędrowca i sprawdź, czy się spotkają.

Zapamiętaj każdą liczbę, którą widziałeś

Intuicja

Przejdź przez ciąg i zapisuj każdą liczbę w zbiorze haszującym. Zanim przejdziesz dalej od danej liczby, sprawdź, czy jest już w zbiorze. Dla 2 zbiór zapełnia się liczbami 2, 4, 16, 37, 58, 89, 145, 42 i 20, a następną wartością jest 4, która już się w nim znajduje: ciąg zamknął pętlę bez napotkania 1, więc 2 nie jest szczęśliwa. Dotarcie do 1 kończy przejście z wynikiem true.

To poprawne, ponieważ następna liczba zależy wyłącznie od bieżącej. Gdy liczba się powtórzy, wszystko, co następuje po niej, będzie powtarzać się dokładnie, więc nie pojawi się żadna nowa liczba, a 1 nigdy się nie pojawi.

Przejście jest krótkie. Pierwszy krok odczytuje O(log n) cyfr liczby n, a każda późniejsza wartość jest mniejsza niż 1000, przy czym żadne przejście nie odwiedza więcej niż 20 różnych liczb, zanim dotrze do 1 lub napotka powtórzenie. Zbiór przechowuje te liczby. Kod w C używa tablicy flag o 1000 elementach jako zbioru i zaczyna zapisywać liczby po pierwszym kroku, gdy każda wartość jest mniejsza niż 1000.

Algorytm

Utwórz pusty zbiór haszujący seen.
Gdy n nie jest równe 1, zwróć false, jeśli n znajduje się w seen.
W przeciwnym razie dodaj n do seen i zastąp n sumą kwadratów jego cyfr.
Gdy pętla się zakończy, n jest równe 1: zwróć true.

def digitSquareSum(n):
    total = 0
    while n > 0:
        digit = n % 10
        total += digit * digit
        n //= 10
    return total


def isHappy(n):
    seen = set()
    while n != 1:
        if n in seen:
            return False  # back at an earlier number: a loop without 1
        seen.add(n)
        n = digitSquareSum(n)
    return True

Szybcy i wolni piechurzy (wykrywanie cyklu Floyda)

Intuicja

Wyobraź sobie każdą liczbę jako węzeł z jedną strzałką wskazującą sumę kwadratów jej cyfr. Podążanie za strzałkami od n prowadzi albo do 1, której strzałka wskazuje z powrotem na 1, albo do pętli. Taki kształt ma lista jednokierunkowa, która może zawierać cykl, a algorytm Floyda wykrywa cykl bez przechowywania czegokolwiek: slow wykonuje jeden krok na rundę, a fast wykonuje dwa.

Jeśli pętla nie zawiera 1, obaj wędrowcy w końcu zaczynają krążyć po niej, a w każdej rundzie fast zyskuje jeden krok względem slow, więc różnica zmniejsza się o jeden, aż staną na tej samej liczbie. Dla 2 spotykają się na 42 po siedmiu rundach. Jeśli wędrówka dociera do 1, fast dociera tam pierwszy i zostaje, ponieważ suma dla 1 wynosi 1. Zatrzymaj więc działanie, gdy fast osiągnie 1 lub wędrowcy się spotkają, i odpowiedz, czy fast wynosi 1.

Dla 7 slow przechodzi przez 7, 49, 97, podczas gdy fast przechodzi przez 49, 130, 1, a pętla kończy się, gdy fast jest na 1. Liczba rund jest co najwyżej małą wielokrotnością długości wędrówki, więc czas działania jest taki sam jak w wersji z użyciem zbioru, a pamięć zajmują dwie liczby całkowite.

Algorytm

Napisz funkcję pomocniczą, która zwraca sumę kwadratów cyfr liczby.
Ustaw slow = n i ustaw fast na liczbę o jeden krok dalej niż n.
Dopóki fast nie jest równe 1 i slow różni się od fast, przesuwaj slow o jeden krok, a fast o dwa kroki.
Zwróć informację, czy fast jest równe 1.

def digitSquareSum(n):
    total = 0
    while n > 0:
        digit = n % 10
        total += digit * digit
        n //= 10
    return total


def isHappy(n):
    slow = n
    fast = digitSquareSum(n)
    # fast moves two steps for every step of slow; they meet only inside a loop.
    while fast != 1 and slow != fast:
        slow = digitSquareSum(slow)
        fast = digitSquareSum(digitSquareSum(fast))
    return fast == 1

Pułapki i przypadki brzegowe

Obliczanie cyfr jest krótkie. Większość błędów dotyczy tego, kiedy pętla się zatrzymuje.

Zapętlenie do momentu, aż wartość wyniesie 1, bez żadnego innego warunku zakończenia. Dla 2 ta pętla nigdy się nie kończy.
Rozpoczęcie od tej samej liczby dla slow i fast oraz sprawdzenie slow != fast przed pierwszym krokiem. Pętla nigdy się nie wykona, a 7 zostanie uznane za nieszczęśliwą. Ustaw fast o jeden krok do przodu albo przesuń oba przed pierwszym porównaniem.
Zwracanie slow == 1 w wersji Floyda. fast osiąga 1 jako pierwszy i pętla natychmiast się zatrzymuje, podczas gdy slow może nadal wskazywać 97.
Dodawanie cyfr zamiast ich kwadratów albo podnoszenie do kwadratu całej liczby. Dla 12 następną wartością jest 1² + 2² = 5, a nie 3 ani 144.
Uznawanie, że n jest nieszczęśliwa, gdy tylko wędrowcy się spotkają. 1 jest odwzorowywane na siebie, więc wędrowcy spotykają się również przy 1; sprawdź, gdzie się spotkali, albo zatrzymaj działanie, gdy fast osiągnie 1.

Najczęstsze pytania4

Dlaczego proces zawsze dochodzi do 1 lub pętli?

Liczba mająca d cyfr jest mapowana na wartość nie większą niż 81 × d, więc duże liczby szybko maleją: każda liczba początkowa nie większa niż 2^31-1 po jednym kroku spada poniżej 1000, a liczba mniejsza niż 1000 jest mapowana na wartość nie większą niż 243. Przebieg jest ograniczony do mniej niż 1000 wartości, więc musi powtórzyć jedną z nich, a od tego momentu cyklicznie się powtarza. 1 jest jedyną liczbą, która jest mapowana na samą siebie.

Jaka jest złożoność czasowa algorytmu sprawdzającego szczęśliwą liczbę?

Pierwszy krok odczytuje O(log n) cyfr liczby n. Każda kolejna wartość jest mniejsza niż 1000, a przebieg powtarza się w ciągu co najwyżej 20 liczb, więc całkowity czas wynosi O(log n). Wersja z tablicą mieszającą przechowuje odwiedzone liczby; wersja Floyda używa O(1) miejsca.

Dlaczego wszystkie nieszczęśliwe liczby kończą na 4?

Sprawdzenie każdej liczby poniżej 1000 pokazuje, że istnieje dokładnie jedna pętla, która nie obejmuje 1: 4, 16, 37, 58, 89, 145, 42, 20 i z powrotem 4. Ponieważ każdy start spada poniżej 1000, każda liczba, która nie jest szczęśliwa, wpada w tę pętlę. Rozwiązanie może zakończyć działanie, gdy tylko napotka 4, ale opiera się to na fakcie, który trzeba byłoby uzasadnić podczas rozmowy kwalifikacyjnej; zbiór i metoda Floyda nie wymagają takiej wiedzy.

Jaki związek ma szczęśliwa liczba z cyklem w liście wiązanej?

Oba pytają, czy podążanie za jedną strzałką z każdego elementu kiedykolwiek prowadzi z powrotem do już odwiedzonego elementu. W przypadku liczby szczęśliwej strzałką jest suma kwadratów cyfr; w liście łączonej jest nią wskaźnik next. Dlatego szybki i wolny wskaźnik Floyda pozwalają rozwiązać oba problemy przy użyciu stałej ilości pamięci.