Armstrong Number

Q: Jaka jest złożoność czasowa sprawdzania, czy liczba jest liczbą Armstronga?

n ma około log n cyfr, tutaj najwyżej 10. Odczytywanie kolejnych cyfr i wyszukiwanie każdej potęgi w tabeli zawierającej dziesięć pozycji zajmuje O(log n) czasu i O(1) pamięci. Ponowne obliczanie d^k za pomocą pętli dla każdej cyfry daje złożoność O(log² n) , ale przy takim rozmiarze nadal działa szybko.

PoczątkującyMatematyka i symulacja

+10

Liczba całkowita dodatnia jest liczbą Armstronga, gdy jest równa sumie swoich cyfr, z których każda jest podniesiona do potęgi równej liczbie jej cyfr. 153 ma trzy cyfry, a 1^3 + 5^3 + 3^3 = 153, więc jest taką liczbą. Napisz funkcję, która przyjmuje n i zwraca true, jeśli jest to liczba Armstronga, a w przeciwnym razie false.

Funkcja

isArmstrong(n: integer) → boolean

ninteger: liczba całkowita dodatnia do sprawdzenia
Zwracaboolean: prawda, gdy n jest równe sumie swoich cyfr, z których każda jest podniesiona do potęgi równej liczbie cyfr

Ograniczenia

1 ≤ n ≤ 10⁹

Przykłady

Wejście: n = 153
Wyjście: true
Wyjaśnienie: 153 ma 3 cyfry, więc każda cyfra jest podnoszona do sześcianu: 1 + 125 + 27 = 153. Suma daje z powrotem tę liczbę, więc odpowiedź to true.

Wejście: n = 10
Wyjście: false
Wyjaśnienie: 10 ma 2 cyfry, więc każda cyfra jest podnoszona do kwadratu: 1 + 0 = 1, co nie jest równe 10. Odpowiedź to false.

Wejście: n = 9474
Wyjście: true
Wyjaśnienie: Dla 4 cyfr potęga wynosi 4: 6561 + 256 + 2401 + 256 = 9474, czyli jest równa samej liczbie, więc odpowiedź to true.

+31 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Tylko 31 liczb Armstronga mieści się w przedziale od 1 do 10^9. Czy potrafisz wymienić je wszystkie, nie testując po kolei miliarda liczb?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Definicją jest algorytm: znajdź liczbę cyfr w n, podnieś każdą cyfrę do tej potęgi, zsumuj wyniki i porównaj z n. Pułapki kryją się w liczbach. Wykładnikiem jest liczba cyfr w tym konkretnym n, a nie stała wartość 3, a suma może przekroczyć zakres liczby całkowitej 32-bitowej: dla 999999999 wynosi 9 × 9^9 = 3486784401.

Odczytaj cyfry z ciągu

Intuicja

Dziesiętny zapis liczby n dostarcza obu potrzebnych rzeczy. Jego długość jest wykładnikiem k, a jego znaki to cyfry. Dla 9474 zapis ma 4 znaki, więc dodajesz 9^4 + 4^4 + 7^4 + 4^4.

Zamień każdy znak z powrotem na jego cyfrę, podnieś ją do potęgi k i dodaj do bieżącej sumy. n jest liczbą Armstronga dokładnie wtedy, gdy końcowa suma jest równa n.

Przechowuj sumę w 64-bitowej liczbie całkowitej. n mieści się w 32 bitach, ale suma nie musi: 999999999 daje 3486784401, czyli więcej niż 32-bitowy limit 2147483647. Obliczenie potęgi za pomocą pętli wykonującej k mnożeń kosztuje k kroków na cyfrę, więc sprawdzenie ma złożoność O(k²), gdzie k jest w przybliżeniu równe log n. W tym przypadku potrzeba najwyżej 100 mnożeń, a zapis zajmuje k znaków pamięci.

Algorytm

Przekształć n w jego zapis dziesiętny i niech k będzie jego długością.
Ustaw 64-bitowe total na 0.
Dla każdego znaku zamień go na cyfrę d i dodaj d^k do total, mnożąc liczby całkowite zamiast wywoływać funkcję potęgującą zmiennoprzecinkową.
Zwróć informację, czy total jest równe n.

def isArmstrong(n):
    digits = str(n)
    k = len(digits)
    total = 0
    for ch in digits:
        total += int(ch) ** k
    return total == n

Rozłóż cyfry i sprawdź ich potęgi

Intuicja

Samo działanie arytmetyczne wykonuje to samo zadanie bez użycia ciągu znaków. m % 10 to ostatnia cyfra liczby m, a dzielenie całkowite przez 10 usuwa ją, więc pętla, która dzieli przez 10, aż nic nie zostanie, zlicza cyfry. 9474 staje się kolejno 947, 94, 9, 0: cztery kroki, czyli k = 4.

Istnieje tylko dziesięć cyfr, więc zanim cokolwiek dodasz, utwórz tablicę powers[d] = d^k dla d od 0 do 9. Obliczenie dla każdej cyfry wymaga wtedy jednego odwołania do tablicy zamiast k mnożeń. Złożoność czasowa sprawdzania spada do O(log n), a tablica ma stały rozmiar równy dziesięć, co oznacza O(1) przestrzeni.

Druga pętla ponownie odrywa cyfry i dodaje powers[m % 10] do sumy. Każdy składnik jest równy zero lub jest dodatni, więc suma nigdy się nie zmniejsza, a gdy tylko przekroczy n, odpowiedzią jest false. Dla 999999999 następuje to po trzech cyfrach, przy 3 × 387420489 = 1162261467. Tablica nadal wymaga 64 bitów, ponieważ n = 10^9 ma dziesięć cyfr, a 9^10 = 3486784401.

Algorytm

Policz cyfry liczby n, dzieląc jej kopię przez 10, aż osiągnie 0; oznacz tę liczbę jako k.
Ustaw powers[d] = d^k dla każdej cyfry d od 0 do 9, używając liczb całkowitych 64-bitowych.
Ponownie dziel nową kopię n przez 10, dodając powers[m % 10] do total na każdym kroku.
Jeśli total przekroczy n, od razu zwróć false.
Po ostatniej cyfrze zwróć informację, czy total jest równe n.

def isArmstrong(n):
    # Count the digits: k is the exponent.
    k = 0
    m = n
    while m > 0:
        k += 1
        m //= 10
    # powers[d] = d^k for the ten possible digits.
    powers = [d ** k for d in range(10)]
    total = 0
    m = n
    while m > 0:
        total += powers[m % 10]
        if total > n:
            return False  # the total only grows
        m //= 10
    return total == n

Pułapki i przypadki brzegowe

Wzór jest krótki, więc błędy wynikają z użytych liczb.

Stały wykładnik równy 3. Akceptuje 153 i 370, ale odrzuca 9474. Odrzuca też każdą jednocyfrową liczbę większą od 1, ponieważ 7^3 = 343.
Suma 32-bitowa. 999999999 daje sumę 3486784401, a wpis w tabeli 9^10 ma tę samą wartość. W C takie przepełnienie powoduje niezdefiniowane zachowanie, Java i C# zawijają wynik do liczby ujemnej, a kompilacja Rust w trybie debugowania powoduje panikę. Użyj long, long long lub i64.
Potęgowanie zmiennoprzecinkowe. pow w C i Math.pow w Javie zwracają wartość typu double. Niektóre środowiska uruchomieniowe C zwracały wartość nieco mniejszą od liczby całkowitej, na przykład 24.999... dla 5^2, którą rzutowanie obcina do 24. Zamiast tego mnoż przez liczby całkowite w pętli.
Porównywanie z niewłaściwą wartością. Pętle przetwarzające cyfry dzielą n, aż osiągnie 0, więc wykonuj obliczenia na kopii i porównaj sumę z pierwotną wartością.
Notacja naukowa. W R as.character(1e9) ma wartość "1e+09" i składa się z pięciu znaków, więc rozwiązanie w R oparte na ciągu znaków formatuje liczbę za pomocą sprintf("%.0f", n).

Najczęstsze pytania4

Czym jest liczba Armstronga?

Liczba Armstronga, nazywana również liczbą narcystyczną, jest równa sumie swoich cyfr, z których każda jest podniesiona do potęgi równej liczbie cyfr. 153 jest taką liczbą, ponieważ 1^3 + 5^3 + 3^3 = 153, a 9474 jest taką liczbą, ponieważ 9^4 + 4^4 + 7^4 + 4^4 = 9474. Każda liczba jednocyfrowa spełnia ten warunek, ponieważ d^1 = d.

Ile jest liczb Armstronga?

W systemie dziesiętnym jest dokładnie 88 dodatnich liczb, a największa ma 39 cyfr. Lista jest skończona, ponieważ liczba mająca k cyfr jest co najmniej równa 10^(k-1), podczas gdy suma potęg jej cyfr jest co najwyżej równa k × 9^k, a od 61 cyfr suma nigdy nie może już dogonić liczby. Między 1 a 10^9 jest ich 31.

Dlaczego sprawdzanie liczby Armstronga wymaga 64-bitowej liczby całkowitej?

Dane wejściowe mieszczą się w 32 bitach, ale suma cyfr podniesionych do potęgi może być kilka razy większa niż sama liczba. 999999999 daje 9 × 9^9 = 3486784401, czyli więcej niż 2^31-1 = 2147483647. Suma przechowywana w 32 bitach przepełni się w tym przypadku, więc przechowuj sumę i potęgi w typie 64-bitowym.

Jaka jest złożoność czasowa sprawdzania, czy liczba jest liczbą Armstronga?

n ma około log n cyfr, tutaj najwyżej 10. Odczytywanie kolejnych cyfr i wyszukiwanie każdej potęgi w tabeli zawierającej dziesięć pozycji zajmuje O(log n) czasu i O(1) pamięci. Ponowne obliczanie d^k za pomocą pętli dla każdej cyfry daje złożoność O(log² n), ale przy takim rozmiarze nadal działa szybko.

Python

def isArmstrong(n):
    # Napisz tutaj kod

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

n = 153

Oczekiwane

true