LeetCode 1134 - Armstrong Number

In this problem, we are given an integer n, and we must determine whether it is an Armstrong number. An Armstrong number is defined as follows: - Let k be the number of digits in n. - Take every digit in the number. - Raise each digit to the power k.

leetcodeeasymath

LeetCode Problem 1134

Difficulty: 🟢 Easy
Topics: Math

Solution

Problem Understanding

In this problem, we are given an integer n, and we must determine whether it is an Armstrong number.

An Armstrong number is defined as follows:

  • Let k be the number of digits in n.
  • Take every digit in the number.
  • Raise each digit to the power k.
  • Sum all those powered values.
  • If the final sum equals the original number n, then n is an Armstrong number.

For example, consider 153:

  • It has 3 digits, so k = 3
  • Its digits are 1, 5, and 3
  • Compute:

$$1^3 + 5^3 + 3^3 = 1 + 125 + 27 = 153$$

Since the sum equals the original number, 153 is an Armstrong number.

The input is a single integer n, and the output is a boolean value:

  • Return true if n is an Armstrong number
  • Return false otherwise

The constraints are:

  • 1 <= n <= 10^8

This tells us the input size is very small. Even the largest possible value has at most 9 digits. Because of this, we do not need sophisticated optimizations. A straightforward digit-processing solution is more than efficient enough.

There are several important edge cases to keep in mind:

  • Single-digit numbers are always Armstrong numbers because any digit d satisfies d^1 = d
  • Numbers containing zeros must still be handled correctly, since 0^k = 0
  • Large numbers near the upper constraint should not overflow during exponentiation
  • We must preserve the original value of n while extracting digits, otherwise we lose the value we need for comparison

Approaches

Brute Force Approach

The brute-force approach would be to repeatedly test every possible combination of digit powers manually or generate all Armstrong numbers within the range and compare against n.

For example, we could:

  1. Iterate through all numbers from 1 to 10^8
  2. For each number:
  • Count its digits
  • Compute the sum of each digit raised to that digit count
  • Store valid Armstrong numbers
  1. Check whether n appears in that set

This works because every number is explicitly verified according to the Armstrong number definition.

However, this approach is extremely wasteful. The problem only asks whether a single number is Armstrong, not to generate all Armstrong numbers in a range. Iterating through millions of unnecessary values would dramatically increase runtime.

Optimal Approach

The key observation is that we only need to evaluate the given number itself.

To determine whether n is an Armstrong number:

  1. Count how many digits the number contains
  2. Extract each digit one by one
  3. Raise each digit to the power of the digit count
  4. Sum these powered values
  5. Compare the sum with the original number

Digit extraction can be done efficiently using modulo and integer division:

  • digit = n % 10 gets the last digit
  • n //= 10 removes the last digit

Since the number has at most 9 digits, the algorithm runs extremely quickly.

Approach Time Complexity Space Complexity Notes
Brute Force O(10^8 × d) O(1) Checks every number in the range unnecessarily
Optimal O(d) O(1) Processes only the input number’s digits

Here, d represents the number of digits in n.

Algorithm Walkthrough

  1. Store the original value of n in another variable.

This is necessary because we will modify n while extracting digits. At the end, we must compare the computed sum against the original number. 2. Determine the number of digits in the number.

Convert the number to a string and compute its length. If n = 153, then the digit count is 3. 3. Initialize a variable to store the running sum.

This variable accumulates the value of each digit raised to the required power. 4. Repeatedly extract the last digit.

Use:

digit = n % 10

This gives the current last digit. 5. Raise the digit to the power of the digit count.

If the digit is 5 and the number has 3 digits:

5 ** 3 = 125

Add this value to the running sum. 6. Remove the last digit from the number.

Use integer division:

n //= 10

This shortens the number for the next iteration. 7. Continue until all digits are processed.

The loop stops once n becomes 0. 8. Compare the computed sum with the original number.

If they are equal, return True. Otherwise, return False.

Why it works

The algorithm directly implements the mathematical definition of an Armstrong number.

Every digit is extracted exactly once, raised to the correct exponent, and added into the total. Since the sum includes all digits and no extra values, the final comparison precisely determines whether the number satisfies the Armstrong property.

Python Solution

class Solution:
    def isArmstrong(self, n: int) -> bool:
        original_number = n
        digit_count = len(str(n))
        
        total = 0
        
        while n > 0:
            digit = n % 10
            total += digit ** digit_count
            n //= 10
        
        return total == original_number

The implementation begins by saving the original number because the variable n will be modified during digit extraction.

Next, the code calculates the number of digits using len(str(n)). This value determines the exponent applied to every digit.

The variable total stores the cumulative sum of powered digits.

Inside the loop:

  • n % 10 extracts the last digit
  • digit ** digit_count computes the powered value
  • The result is added into total
  • n //= 10 removes the processed digit

Once all digits are processed, the computed total is compared with the original number. If they match, the number is an Armstrong number.

Go Solution

func isArmstrong(n int) bool {
    originalNumber := n
    
    digitCount := len([]rune(string(rune(n))))
    
    temp := n
    digitCount = 0
    
    for temp > 0 {
        digitCount++
        temp /= 10
    }
    
    total := 0
    
    for n > 0 {
        digit := n % 10
        
        power := 1
        for i := 0; i < digitCount; i++ {
            power *= digit
        }
        
        total += power
        n /= 10
    }
    
    return total == originalNumber
}

The Go solution follows the same logic as the Python implementation, but Go does not provide a built-in exponentiation operator for integers. Because of this, exponentiation is implemented manually using a loop.

Another difference is digit counting. In Go, we typically count digits numerically instead of converting to a string. A temporary variable is repeatedly divided by 10 until it becomes 0.

The solution uses only integer arithmetic, so there are no floating-point precision issues.

Worked Examples

Example 1

Input:

n = 153

The number has 3 digits.

Iteration Current n Extracted Digit Digit^3 Running Total
1 153 3 27 27
2 15 5 125 152
3 1 1 1 153

Final comparison:

153 == 153

Result:

true

Example 2

Input:

n = 123

The number has 3 digits.

Iteration Current n Extracted Digit Digit^3 Running Total
1 123 3 27 27
2 12 2 8 35
3 1 1 1 36

Final comparison:

36 != 123

Result:

false

Complexity Analysis

Measure Complexity Explanation
Time O(d) Each digit is processed exactly once
Space O(1) Only a few variables are used

The runtime depends only on the number of digits in the input number. Since the maximum input is 10^8, there are at most 9 digits, making the algorithm extremely efficient.

The algorithm uses constant extra memory because it stores only a few integer variables regardless of input size.

Test Cases

solution = Solution()

assert solution.isArmstrong(153) == True   # classic Armstrong number
assert solution.isArmstrong(123) == False  # standard non-Armstrong number

assert solution.isArmstrong(1) == True     # single-digit number
assert solution.isArmstrong(5) == True     # another single-digit number
assert solution.isArmstrong(9) == True     # largest single-digit number

assert solution.isArmstrong(10) == False   # contains zero, not Armstrong
assert solution.isArmstrong(370) == True   # known Armstrong number
assert solution.isArmstrong(371) == True   # known Armstrong number
assert solution.isArmstrong(407) == True   # known Armstrong number

assert solution.isArmstrong(9474) == True  # 4-digit Armstrong number
assert solution.isArmstrong(9475) == False # close but invalid

assert solution.isArmstrong(8208) == True  # another valid Armstrong number
assert solution.isArmstrong(9926315) == True  # larger Armstrong number

assert solution.isArmstrong(100000000) == False  # upper constraint boundary
Test Why
153 Basic Armstrong number
123 Basic non-Armstrong number
1 Smallest valid input
5 Single-digit Armstrong property
9 Largest single-digit case
10 Includes zero digit
370 Known Armstrong number
371 Another classic Armstrong number
407 Valid 3-digit Armstrong number
9474 Valid 4-digit Armstrong number
9475 Near-valid number
8208 Larger valid Armstrong number
9926315 Stress test with many digits
100000000 Upper constraint boundary

Edge Cases

Single-Digit Numbers

Every single-digit number is automatically an Armstrong number because the digit count is 1. Any digit d satisfies:

$$d^1 = d$$

A common mistake is forgetting this property and incorrectly handling small inputs. The implementation handles this naturally because the exponent becomes 1.

Numbers Containing Zeroes

Numbers like 10 or 407 contain zero digits. Some implementations accidentally skip zeros or mishandle exponentiation involving zero.

This solution processes every digit uniformly. Since 0^k = 0, zeros contribute correctly to the total sum.

Large Inputs Near the Constraint Limit

The upper bound is 10^8, which can contain up to 9 digits. Repeated exponentiation could appear risky for overflow in some languages.

The implementation remains safe because:

  • The constraints are small
  • Integer operations stay within standard 32-bit integer limits
  • Only a few digits are processed

The algorithm therefore handles the maximum allowed input efficiently and correctly.