Problem Description

An Armstrong number (also known as a narcissistic number) is a special type of number where the sum of each digit raised to the power of the total number of digits equals the number itself.

Given an integer n, you need to determine if it's an Armstrong number.

For a k-digit number to be an Armstrong number:

• Count the total number of digits (k)
• Take each digit and raise it to the kth power
• Sum all these powered values
• If the sum equals the original number n, then it's an Armstrong number

Examples:

• 153 is an Armstrong number because it has 3 digits, and 1³ + 5³ + 3³ = 1 + 125 + 27 = 153
• 9474 is an Armstrong number because it has 4 digits, and 9⁴ + 4⁴ + 7⁴ + 4⁴ = 6561 + 256 + 2401 + 256 = 9474
• 123 is not an Armstrong number because 1³ + 2³ + 3³ = 1 + 8 + 27 = 36 ≠ 123

The solution works by:

1. Finding the number of digits k in the number
2. Extracting each digit using modulo operation (x % 10)
3. Raising each digit to the power k and accumulating the sum
4. Comparing the final sum with the original number

Intuition

The key insight is that we need to check if a number equals the sum of its own digits each raised to a specific power. This naturally leads us to think about extracting individual digits from the number.

To extract digits from a number, we can use the modulo operation. When we do n % 10, we get the last digit. Then dividing by 10 (n // 10) removes that last digit. We can repeat this process until we've extracted all digits.

But before we start extracting digits, we need to know what power to raise them to. The problem states it's the kth power where k is the total number of digits. The simplest way to find the number of digits is to convert the number to a string and check its length: len(str(n)).

Once we know k, we can iterate through the number, extracting each digit one by one:

• Get the last digit with x % 10
• Raise it to the power k
• Add it to our running sum
• Remove the last digit with x // 10
• Continue until no digits remain

After processing all digits, we simply compare our calculated sum with the original number. If they match, we've found an Armstrong number.

This approach is straightforward because it directly implements the mathematical definition: we're literally computing the sum of each digit raised to the kth power and checking if it equals n.

Learn more about Math patterns.

Solution Approach

The implementation follows a simulation approach where we directly calculate the sum of each digit raised to the kth power.

Step 1: Calculate the number of digits

k = len(str(n))

We convert the number to a string and get its length. This gives us k, the total number of digits.

Step 2: Initialize variables

s, x = 0, n

• s is initialized to 0 to store the running sum of powered digits
• x is a copy of n that we'll manipulate to extract digits (we preserve the original n for comparison)

Step 3: Extract digits and calculate the sum

while x:
    s += (x % 10) ** k
    x //= 10

This loop continues while x has remaining digits:

• x % 10 extracts the last digit
• (x % 10) ** k raises that digit to the kth power
• We add this value to our sum s
• x //= 10 removes the last digit by integer division

For example, if n = 153:

• First iteration: x = 153, extract 3, add 3³ = 27 to sum, x becomes 15
• Second iteration: x = 15, extract 5, add 5³ = 125 to sum, x becomes 1
• Third iteration: x = 1, extract 1, add 1³ = 1 to sum, x becomes 0
• Loop ends, s = 27 + 125 + 1 = 153

Step 4: Check if it's an Armstrong number

return s == n

We return True if the calculated sum equals the original number, False otherwise.

The time complexity is O(log n) since we process each digit once, and the number of digits is proportional to log n. The space complexity is O(1) as we only use a constant amount of extra space.

Example Walkthrough

Let's walk through the solution with n = 371:

Step 1: Calculate the number of digits

• Convert 371 to string: "371"
• Count digits: k = 3

Step 2: Initialize variables

• s = 0 (to accumulate the sum)
• x = 371 (working copy of the number)

Step 3: Extract digits and calculate powers

Iteration 1:

• Current x = 371
• Extract last digit: 371 % 10 = 1
• Calculate power: 1³ = 1
• Add to sum: s = 0 + 1 = 1
• Remove last digit: x = 371 // 10 = 37

Iteration 2:

• Current x = 37
• Extract last digit: 37 % 10 = 7
• Calculate power: 7³ = 343
• Add to sum: s = 1 + 343 = 344
• Remove last digit: x = 37 // 10 = 3

Iteration 3:

• Current x = 3
• Extract last digit: 3 % 10 = 3
• Calculate power: 3³ = 27
• Add to sum: s = 344 + 27 = 371
• Remove last digit: x = 3 // 10 = 0

Loop ends (x = 0)

Step 4: Check result

• Compare: s == n → 371 == 371 → True
• Therefore, 371 is an Armstrong number!

We can verify: 3³ + 7³ + 1³ = 27 + 343 + 1 = 371 ✓

Solution Implementation

Time and Space Complexity

The time complexity is O(log n). This is because the while loop iterates through each digit of the number n. The number of digits in n is ⌊log₁₀(n)⌋ + 1, which is O(log n). Each iteration performs constant time operations (modulo, exponentiation with a fixed exponent k, integer division, and addition).

The space complexity is O(log n). Although the algorithm uses only a constant number of variables (k, s, x), the initial conversion str(n) creates a string representation of the number which requires O(log n) space to store all the digits. Additionally, the exponentiation operation (x % 10) ** k may require O(log n) space internally depending on the implementation, as k itself is O(log n) and computing large powers may use additional space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow in Other Languages

While Python handles arbitrarily large integers automatically, in languages like Java or C++, calculating digit ** k for large digits and powers can cause integer overflow. For example, 9^9 = 387,420,489 which fits in a 32-bit integer, but 9^10 = 3,486,784,401 exceeds it.

Solution: Use appropriate data types (like long long in C++ or long in Java) or implement overflow checking:

# Python doesn't have this issue, but in other languages:
# Check if the sum would overflow before adding
if sum_of_powers > MAX_INT - (digit ** num_digits):
    return False  # Can't be Armstrong number if it overflows

2. Handling Edge Cases (0 and Single Digits)

The code might not handle edge cases correctly depending on the problem's definition. Is 0 an Armstrong number? (0^1 = 0)? Are single-digit numbers Armstrong numbers? (5^1 = 5)?

Solution: Clarify requirements and add explicit handling:

def isArmstrong(self, n: int) -> bool:
    if n < 0:
        return False  # Negative numbers typically aren't considered
    if n == 0:
        return True  # 0^1 = 0, so it's an Armstrong number
    # Continue with regular logic...

3. String Conversion Performance

Using len(str(n)) to count digits involves string conversion, which has overhead and might be slower for very large numbers.

Solution: Use mathematical approach to count digits:

def count_digits(n):
    if n == 0:
        return 1
    count = 0
    temp = n
    while temp > 0:
        count += 1
        temp //= 10
    return count

# Or using logarithm (be careful with edge cases)
import math
num_digits = 1 if n == 0 else math.floor(math.log10(n)) + 1

4. Modifying the Original Number

A common mistake is accidentally modifying n directly instead of using a copy, then comparing against the modified value:

# Wrong approach:
while n > 0:  # Modifying n directly
    s += (n % 10) ** k
    n //= 10
return s == n  # n is now 0, not the original value!

Solution: Always work with a copy of the original number as shown in the correct implementation.

5. Inefficient Power Calculation

For very large values of k, using ** operator repeatedly might be inefficient if not optimized by the language.

Solution: Consider caching power calculations if checking multiple numbers:

def isArmstrong(self, n: int) -> bool:
    num_digits = len(str(n))
  
    # Pre-calculate powers for digits 0-9
    powers = [i ** num_digits for i in range(10)]
  
    sum_of_powers = 0
    temp_number = n
  
    while temp_number > 0:
        digit = temp_number % 10
        sum_of_powers += powers[digit]  # Use pre-calculated value
        temp_number //= 10
  
    return sum_of_powers == n