1134. Armstrong Number
Model: qwen2.5-coder:14b
Topics: Math
FAANG asked: 1
Acceptance rate: 78.1%
Problem Breakdown
The problem asks us to determine if a given integer n is an Armstrong number. An Armstrong number is defined as a k-digit number where the sum of each digit raised to the power of k equals the original number n. The input is a single integer n, and the output should be a boolean indicating whether n is an Armstrong number or not.
Inputs:
- An integer
n(1 <= n <= 10^8)
Outputs:
- A boolean value (
trueifnis an Armstrong number,falseotherwise)
Implicit Constraints/Edge Cases:
- The input is always a positive integer within the given range.
- Single-digit numbers are trivially Armstrong numbers since they satisfy the condition by definition.
Intuition
A brute-force approach would involve converting the number to a string to easily iterate over each digit, raising each digit to the power of k (the number of digits), and summing these values. If the sum equals the original number, it is an Armstrong number. However, this approach is straightforward but not optimal in terms of time complexity.
The key insight is that we can avoid converting the number to a string by using mathematical operations to extract each digit. This reduces the overhead associated with string manipulation and maintains the same logic.
Approach
- Determine the Number of Digits (
k): Use logarithmic operations to find the number of digits inn. - Initialize Sum: Start with a sum variable initialized to 0.
- Extract Digits and Compute Power Sum:
- While
nis greater than 0, extract each digit using modulo operation (n % 10). - Raise the extracted digit to the power of
k. - Add this value to the sum.
- Remove the last digit from
nby performing integer division (n //= 10).
- While
- Compare Sum with Original Number: After processing all digits, compare the computed sum with the original number
n. If they are equal, returntrue; otherwise, returnfalse.
Complexity Analysis
- Time Complexity: O(k), where
kis the number of digits inn. This is because we iterate over each digit exactly once. - Space Complexity: O(1). We use a constant amount of extra space regardless of the input size.
Solution
def isArmstrong(n: int) -> bool:
# Determine the number of digits (k)
k = len(str(n))
# Initialize sum to 0
total_sum = 0
# Copy of n for comparison later
original_n = n
# Extract each digit and compute the power sum
while n > 0:
digit = n % 10
total_sum += digit ** k
n //= 10
# Compare the computed sum with the original number
return total_sum == original_n
Edge Cases Handled
- Single-digit numbers: These are trivially Armstrong numbers since they satisfy the condition by definition.
- Numbers with repeated digits: The algorithm correctly handles cases where all digits are the same (e.g., 111, 222).
- Largest possible input (
n = 10^8): The solution efficiently processes large numbers within the given constraints.