Armstrong Number

Q: 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) .

BeginnerMath and simulation

+10

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

isArmstrong(n: integer) → boolean

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 ≤ 10⁹

Examples

Input: n = 153
Output: true
Explanation: 153 has 3 digits, so every digit is cubed: 1 + 125 + 27 = 153. The sum gives back the number, so the answer is true.

Input: n = 10
Output: false
Explanation: 10 has 2 digits, so every digit is squared: 1 + 0 = 1, which is not 10. The answer is false.

Input: n = 9474
Output: true
Explanation: With 4 digits the power is 4: 6561 + 256 + 2401 + 256 = 9474, the number itself, so the answer is true.

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.

0 of 3 opened

Solution

The definition is the algorithm: count the digits of n, raise every digit to that power, add the results and compare with n. The exponent is the digit count of this n, not a fixed 3, and the sum can outgrow 32 bits: 999999999 gives 9 × 9^9 = 3486784401.

Read the digits from the string

Intuition

The decimal string of n gives you both things you need: its length is the exponent k, and its characters are the digits. For 9474 you add 9^4 + 4^4 + 7^4 + 4^4. n is an Armstrong number exactly when the total equals n.

A power computed with k multiplications costs k steps per digit, so the check is O(k²) with k about log n: at most 100 multiplications here.

Algorithm

Convert n to its decimal string and let k be its length.
Set a 64-bit total to 0.
For every character, turn it into its digit d and add d^k to total, multiplying whole numbers rather than calling a floating point power.
Return whether total equals n.

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

Peel the digits and look up their powers

Intuition

Arithmetic does the same job without a string. m % 10 is the last digit of m and integer division by 10 drops it, so dividing until nothing is left counts the digits: 9474 becomes 947, 94, 9, 0, so k = 4.

Only ten digits exist, so build powers[d] = d^k for d from 0 to 9 first. Each digit then costs one lookup instead of k multiplications: O(log n) time and O(1) space.

Every term is zero or positive, so once the total passes n the answer is false. For 999999999 that happens after three digits, at 3 × 387420489 = 1162261467.

Algorithm

Count the digits of n by dividing a copy by 10 until it reaches 0; call the count k.
Fill powers[d] = d^k for every digit d from 0 to 9, in 64-bit integers.
Divide a fresh copy of n by 10 again, adding powers[m % 10] to total at each step.
If total passes n, return false at once.
After the last digit, return whether total equals 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

Pitfalls and edge cases

A fixed exponent of 3. It accepts 153 and 370 but rejects 9474 and every one-digit number above 1, since 7^3 = 343.
A 32-bit sum. 999999999 sums to 3486784401, and for n = 10^9 the table entry 9^10 is the same number. C overflows into undefined behavior, Java and C# wrap to a negative number, and a Rust debug build panics.
Floating point powers. Some C runtimes have returned 24.999... for pow(5, 2), which a cast truncates to 24. Multiply whole numbers instead.
Comparing with the wrong value. The digit loops divide n down to 0, so work on a copy.
Scientific notation in R. as.character(1e9) is "1e+09", five characters; format with sprintf("%.0f", n).

Frequently asked questions3

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. 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 k digit number is at least 10^(k-1), while its digit power sum is at most k × 9^k, and from 61 digits on the sum cannot catch up.

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).

def isArmstrong(n):
    # Write code here

Test #1

Test #2

Test #3

Argument

n = 153

Expected Output

true