Armstrong Number

Q: Wie hoch ist die Zeitkomplexität beim Überprüfen einer Armstrong-Zahl?

n hat ungefähr log n Stellen, hier höchstens 10. Die Ziffern einzeln abzutrennen und jede Potenz in einer Tabelle mit zehn Einträgen nachzuschlagen, benötigt O(log n) Zeit und O(1) Speicherplatz. Wenn man d^k für jede Ziffer mit einer Schleife neu berechnet, ergibt sich O(log² n) — bei dieser Größe immer noch schnell.

EinsteigerMathe und Simulation

+10

Eine positive ganze Zahl ist eine Armstrong-Zahl, wenn sie der Summe ihrer eigenen Ziffern entspricht, wobei jede Ziffer auf die Potenz der Anzahl ihrer Ziffern erhoben wird. 153 hat drei Ziffern und 1^3 + 5^3 + 3^3 = 153, also ist sie eine Armstrong-Zahl. Schreibe eine Funktion, die n erhält und true zurückgibt, wenn es eine Armstrong-Zahl ist, und andernfalls false.

Funktion

isArmstrong(n: integer) → boolean

ninteger: die zu testende positive Ganzzahl
Gibt zurückboolean: wahr, wenn n der Summe seiner Ziffern entspricht, wobei jede Ziffer mit der Anzahl der Ziffern potenziert wird

Einschränkungen

1 ≤ n ≤ 10⁹

Beispiele

Eingabe: n = 153
Ausgabe: true
Erklärung: 153 hat 3 Ziffern, also wird jede Ziffer hoch drei genommen: 1 + 125 + 27 = 153. Die Summe ergibt wieder die Zahl, daher lautet die Antwort true.

Eingabe: n = 10
Ausgabe: false
Erklärung: 10 hat 2 Ziffern, also wird jede Ziffer quadriert: 1 + 0 = 1, was nicht 10 ist. Die Antwort ist false.

Eingabe: n = 9474
Ausgabe: true
Erklärung: Bei 4 Ziffern ist die Potenz 4: 6561 + 256 + 2401 + 256 = 9474, also die Zahl selbst, daher lautet die Antwort true.

+31 versteckte Tests beim Einreichen

Weiterführende Frage

Zwischen 1 und 10^9 liegen nur 31 Armstrong-Zahlen. Kannst du sie alle auflisten, ohne eine Milliarde Zahlen einzeln zu testen?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Die Definition ist der Algorithmus: Ermittle, wie viele Ziffern n hat, potenziere jede Ziffer mit dieser Zahl, addiere die Ergebnisse und vergleiche sie mit n. Die Tücken liegen in den Zahlen. Der Exponent ist die Ziffernanzahl dieses konkreten n, nicht eine feste 3, und die Summe kann den Wertebereich einer 32-Bit-Ganzzahl überschreiten: Für 999999999 ist sie 9 × 9^9 = 3486784401.

Lies die Ziffern aus der Zeichenfolge

Idee

Die Dezimaldarstellung von n liefert dir beides, was du brauchst. Ihre Länge ist der Exponent k, und ihre Zeichen sind die Ziffern. Bei 9474 hat die Zeichenfolge 4 Zeichen, also addierst du 9^4 + 4^4 + 7^4 + 4^4.

Wandle jedes Zeichen wieder in seine Ziffer um, potenziere diese mit dem Exponenten k und addiere sie zu einer laufenden Summe. n ist genau dann eine Armstrong-Zahl, wenn die fertige Summe gleich n ist.

Speichere die Summe in einer 64-Bit-Ganzzahl. n passt in 32 Bit, aber die Summe muss es nicht: 999999999 ergibt 3486784401 und liegt damit über dem 32-Bit-Limit von 2147483647. Eine Potenz, die mit einer Schleife aus k Multiplikationen berechnet wird, kostet pro Ziffer k Schritte; daher ist die Prüfung O(k²), wobei k ungefähr log n beträgt. Hier sind das höchstens 100 Multiplikationen, und die Zeichenfolge benötigt k Zeichen Speicher.

Algorithmus

Wandle n in seine Dezimalzeichenfolge um und setze k auf ihre Länge.
Setze eine 64-Bit-Variable total auf 0.
Wandle jedes Zeichen in seine Ziffer d um und addiere d^k zu total, indem du ganze Zahlen multiplizierst, statt eine Gleitkomma-Potenzfunktion aufzurufen.
Gib zurück, ob total gleich n ist.

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

Zerlege die Ziffern und schlage ihre Potenzen nach

Idee

Arithmetik allein erfüllt denselben Zweck, ohne einen String zu verwenden. m % 10 ist die letzte Ziffer von m, und die Ganzzahldivision durch 10 entfernt sie. Eine Schleife, die so lange durch 10 teilt, bis nichts mehr übrig ist, zählt also die Ziffern. Aus 9474 wird 947, 94, 9, 0: vier Schritte, also k = 4.

Es gibt nur zehn Ziffern. Erstelle daher eine Tabelle powers[d] = d^k für d von 0 bis 9, bevor du irgendetwas addierst. Für jede Ziffer ist dann nur noch ein Tabellenzugriff statt k Multiplikationen nötig. Die Prüfung benötigt nun O(log n) Zeit, und die Tabelle hat eine feste Größe von zehn, benötigt also O(1) Speicherplatz.

Die zweite Schleife zerlegt die Zahl erneut in ihre Ziffern und addiert powers[m % 10] zur Summe. Jeder Summand ist null oder positiv, die Summe wird also nie kleiner. Sobald sie n überschreitet, lautet die Antwort false. Bei 999999999 geschieht das nach drei Ziffern, bei 3 × 387420489 = 1162261467. Die Tabelle benötigt weiterhin 64 Bit, denn n = 10^9 hat zehn Ziffern und 9^10 = 3486784401.

Algorithmus

Zähle die Ziffern von n, indem du eine Kopie durch 10 teilst, bis sie 0 erreicht; nenne die Anzahl k.
Fülle powers[d] = d^k für jede Ziffer d von 0 bis 9 mit 64-Bit-Ganzzahlen.
Teile erneut eine frische Kopie von n durch 10 und addiere bei jedem Schritt powers[m % 10] zu total.
Wenn total größer als n wird, gib sofort false zurück.
Gib nach der letzten Ziffer zurück, ob total gleich n ist.

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

Stolperfallen und Grenzfälle

Die Formel ist kurz, daher entstehen die Fehler durch die Zahlen, die damit verarbeitet werden.

Ein fester Exponent von 3. Die Formel akzeptiert 153 und 370, lehnt aber 9474 ab. Außerdem lehnt sie jede einstellige Zahl größer als 1 ab, da 7^3 = 343.
Eine 32-Bit-Summe. Die Summe der Ziffern von 999999999 ergibt 3486784401, und der Tabelleneintrag 9^10 ist dieselbe Zahl. In C ist dieser Überlauf undefiniertes Verhalten, Java und C# wickeln den Wert zu einer negativen Zahl um, und ein Rust-Debug-Build löst eine Panic aus. Verwende long, long long oder i64.
Gleitkommapotenzen. pow in C und Math.pow in Java geben einen double zurück. Einige C-Laufzeitumgebungen haben einen Wert zurückgegeben, der geringfügig unter einer ganzen Zahl lag, etwa 24.999... für 5^2, was beim Umwandeln zu 24 abgeschnitten wird. Multipliziere stattdessen in einer Schleife ganze Zahlen.
Vergleich mit dem falschen Wert. Die Ziffernschleifen dividieren n herunter bis auf 0. Arbeite daher mit einer Kopie und vergleiche die Summe mit dem ursprünglichen Wert.
Wissenschaftliche Schreibweise. In R ist as.character(1e9) gleich "1e+09", also fünf Zeichen lang. Daher formatiert eine stringbasierte R-Lösung den Wert mit sprintf("%.0f", n).

Häufige Fragen4

Was ist eine Armstrong-Zahl?

Eine Armstrong-Zahl, auch narzisstische Zahl genannt, entspricht der Summe ihrer eigenen Ziffern, wobei jede Ziffer zur Potenz der Anzahl der Ziffern erhoben wird. 153 ist eine solche Zahl, weil 1^3 + 5^3 + 3^3 = 153, und 9474 ist eine solche Zahl, weil 9^4 + 4^4 + 7^4 + 4^4 = 9474. Jede einstellige Zahl erfüllt diese Bedingung, da d^1 = d.

Wie viele Armstrong-Zahlen gibt es?

Zur Basis 10 gibt es genau 88 positive Einsen, und die größte hat 39 Ziffern. Die Liste ist endlich, weil eine Zahl mit k Ziffern mindestens 10^(k-1) beträgt, während ihre Ziffern-Potenzsumme höchstens k × 9^k beträgt, und ab 61 Ziffern kann die Summe niemals aufholen. Zwischen 1 und 10^9 gibt es 31.

Warum benötigt die Prüfung auf Armstrong-Zahlen eine 64-Bit-Ganzzahl?

Die Eingabe passt in 32 Bit, aber die Summe der potenzierten Ziffern kann um ein Vielfaches größer sein als die Zahl. 999999999 ergibt 9 × 9^9 = 3486784401 und liegt damit über 2^31-1 = 2147483647. Eine 32-Bit-Summe läuft dabei über, also solltest du die Summe und die Potenzen in einem 64-Bit-Typ speichern.

Wie hoch ist die Zeitkomplexität beim Überprüfen einer Armstrong-Zahl?

n hat ungefähr log n Stellen, hier höchstens 10. Die Ziffern einzeln abzutrennen und jede Potenz in einer Tabelle mit zehn Einträgen nachzuschlagen, benötigt O(log n) Zeit und O(1) Speicherplatz. Wenn man d^k für jede Ziffer mit einer Schleife neu berechnet, ergibt sich O(log² n) — bei dieser Größe immer noch schnell.

Python

def isArmstrong(n):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

n = 153

Erwartet

true