Armstrong Number
A positive integer is an Armstrong number when it equals the sum of its own digits, each raised to the power of how many digits it has. 153 has three digits and 1^3 + 5^3 + 3^3 = 153, so it is one. Write a function that gets n and returns true if it is an Armstrong number and false otherwise.
Function
- ninteger
- the positive integer to test
- Returnsboolean
- true when n equals the sum of its digits, each raised to the number of digits
Constraints
1 ≤ n ≤ 109
Examples
- Input
- n = 153
- Output
- true
- Explanation
153has 3 digits, so every digit is cubed:1 + 125 + 27 = 153. The sum gives back the number, so the answer istrue.
- Input
- n = 10
- Output
- false
- Explanation
10has 2 digits, so every digit is squared:1 + 0 = 1, which is not10. The answer isfalse.
- Input
- n = 9474
- Output
- true
- Explanation
- With 4 digits the power is 4:
6561 + 256 + 2401 + 256 = 9474, the number itself, so the answer istrue.
+31 hidden tests on Submit
Follow-up
Only 31 Armstrong numbers lie between 1 and 10^9. Can you list all of them without testing a billion numbers one by one?
Hints
Open them one at a time. Each one gives away a little more.
Before you can raise a digit to a power you need the exponent. How many digits does
nhave, and how can you find out with arithmetic?n % 10is the last digit and integer division by 10 removes it. Repeat until nothing is left: that visits every digit, and the number of steps is the exponentk.Count the digits in one pass. Then peel them again, add each digit raised to the power
kto a 64-bit total, and return whether the total equals the originaln.
Solution
The definition is the algorithm: find how many digits n has, raise every digit to that power, add the results and compare with n. The traps are in the numbers. The exponent is the digit count of this particular n, not a fixed 3, and the sum can outgrow a 32-bit integer: for 999999999 it is 9 × 9^9 = 3486784401.
Read the digits from the string
Intuition
The decimal string of n hands you both things you need. Its length is the exponent k, and its characters are the digits. For 9474 the string has 4 characters, so you add 9^4 + 4^4 + 7^4 + 4^4.
Turn each character back into its digit, raise it to the power k and add it to a running total. n is an Armstrong number exactly when the finished total equals n.
Keep the total in a 64-bit integer. n fits in 32 bits, but the sum does not have to: 999999999 gives 3486784401, above the 32-bit limit of 2147483647. A power computed with a loop of k multiplications costs k steps per digit, so the check is O(k²) with k about log n. Here that is at most 100 multiplications, and the string costs k characters of memory.
Algorithm
- Convert
nto its decimal string and letkbe its length. - Set a 64-bit
totalto0. - For every character, turn it into its digit
dand addd^ktototal, multiplying whole numbers rather than calling a floating point power. - Return whether
totalequalsn.
def isArmstrong(n):
digits = str(n)
k = len(digits)
total = 0
for ch in digits:
total += int(ch) ** k
return total == nPeel the digits and look up their powers
Intuition
Arithmetic alone does the same job without a string. m % 10 is the last digit of m and integer division by 10 drops it, so a loop that divides by 10 until nothing is left counts the digits. 9474 becomes 947, 94, 9, 0: four steps, so k = 4.
Only ten digits exist, so build a table powers[d] = d^k for d from 0 to 9 before you add anything. Each digit then costs one lookup instead of k multiplications. The check drops to O(log n) time, and the table has a fixed size of ten, which is O(1) space.
The second loop peels the digits again and adds powers[m % 10] to the total. Every term is zero or positive, so the total never shrinks, and once it passes n the answer is false. For 999999999 that happens after three digits, at 3 × 387420489 = 1162261467. The table still needs 64 bits, because n = 10^9 has ten digits and 9^10 = 3486784401.
Algorithm
- Count the digits of
nby dividing a copy by 10 until it reaches 0; call the countk. - Fill
powers[d] = d^kfor every digitdfrom 0 to 9, in 64-bit integers. - Divide a fresh copy of
nby 10 again, addingpowers[m % 10]tototalat each step. - If
totalpassesn, returnfalseat once. - After the last digit, return whether
totalequalsn.
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
Pitfalls and edge cases
The formula is short, so the bugs come from the numbers around it.
- A fixed exponent of 3. It accepts
153and370but rejects9474, and it rejects every one-digit number above 1, since7^3 = 343. - A 32-bit sum.
999999999sums to3486784401and the table entry9^10is the same number. In C that overflow is undefined behavior, Java and C# wrap to a negative number, and a Rust debug build panics. Uselong,long longori64. - Floating point powers.
powin C andMath.powin Java return adouble. Some C runtimes have returned a value a little below a whole number, such as24.999...for5^2, which a cast truncates to24. Multiply whole numbers in a loop instead. - Comparing against the wrong value. The digit loops divide
ndown to 0, so work on a copy and compare the total with the original. - Scientific notation. In R,
as.character(1e9)is"1e+09", five characters, so a string based R solution formats withsprintf("%.0f", n).
Frequently asked questions4
What is an Armstrong number?
An Armstrong number, also called a narcissistic number, equals the sum of its own digits, each raised to the power of the number of digits. 153 is one because 1^3 + 5^3 + 3^3 = 153, and 9474 is one because 9^4 + 4^4 + 7^4 + 4^4 = 9474. Every one-digit number qualifies, since d^1 = d.
How many Armstrong numbers are there?
In base 10 there are exactly 88 positive ones, and the largest has 39 digits. The list is finite because a number with k digits is at least 10^(k-1), while its digit power sum is at most k × 9^k, and from 61 digits on the sum can never catch up. Between 1 and 10^9 there are 31.
Why does the Armstrong number check need a 64-bit integer?
The input fits in 32 bits, but the sum of powered digits can be several times larger than the number. 999999999 gives 9 × 9^9 = 3486784401, above 2^31-1 = 2147483647. A 32-bit total overflows there, so keep the total and the powers in a 64-bit type.
What is the time complexity of checking an Armstrong number?
n has about log n digits, at most 10 here. Peeling the digits and looking each power up in a table of ten is O(log n) time and O(1) space. Recomputing d^k with a loop for every digit makes it O(log² n), still fast at this size.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
Python
def isArmstrong(n):
# Write code hereCase 1
Case 2
Case 3
Input
n = 153
Expected
true