Armstrong Number

Description

Given a positive integer n, determine whether it is an Armstrong number (also known as a Narcissistic number or Pluperfect Digital Invariant).

A number is called an Armstrong number if the sum of each of its digits raised to the power of the total number of digits equals the number itself.

Formally, a k-digit number n with digits d₁, d₂, ..., dₖ is Armstrong if:

n = d₁ᵏ + d₂ᵏ + d₃ᵏ + ... + dₖᵏ

For example:

153 has 3 digits: 1³ + 5³ + 3³ = 1 + 125 + 27 = 153 ✓
9474 has 4 digits: 9⁴ + 4⁴ + 7⁴ + 4⁴ = 6561 + 256 + 2401 + 256 = 9474 ✓
123 has 3 digits: 1³ + 2³ + 3³ = 1 + 8 + 27 = 36 ≠ 123 ✗

Armstrong numbers are a fascinating concept in recreational number theory. In base 10, there are only 88 Armstrong numbers in total, and the largest has 39 digits. The concept was named after Michael F. Armstrong and is closely related to the mathematical study of fixed points of digit-power functions.

Examples

Example 1

Input: n = 153

Output: true

Explanation: 153 has 3 digits. Compute: 1³ + 5³ + 3³ = 1 + 125 + 27 = 153. The sum equals the original number, so 153 is an Armstrong number.

Example 2

Input: n = 9474

Output: true

Explanation: 9474 has 4 digits. Compute: 9⁴ + 4⁴ + 7⁴ + 4⁴ = 6561 + 256 + 2401 + 256 = 9474. The sum equals the number, so 9474 is an Armstrong number.

Example 3

Input: n = 372

Output: false

Explanation: 372 has 3 digits. Compute: 3³ + 7³ + 2³ = 27 + 343 + 8 = 378. Since 378 ≠ 372, it is not an Armstrong number.

Example 4

Input: n = 100

Output: false

Explanation: 100 has 3 digits. Compute: 1³ + 0³ + 0³ = 1 + 0 + 0 = 1. Since 1 ≠ 100, it is not an Armstrong number. Notice how zeros contribute nothing to the sum.

Constraints

100 ≤ n < 1000

(The input is a 3-digit number, so the order k = 3 and we always compute the sum of cubes of digits.)

Editorial

Brute Force

Intuition

The most direct approach follows the definition step by step: extract every digit, compute its cube (since we're dealing with 3-digit numbers), sum them up, and compare with the original number.

The process of extracting digits from a number is a fundamental building block in many number-theory problems. We use two operations repeatedly:

n % 10 gives the last digit (the remainder when dividing by 10)
n / 10 removes the last digit (integer division by 10)

Think of it like unpacking a number from right to left. For 153:

153 % 10 = 3 (last digit), then 153 / 10 = 15
15 % 10 = 5 (next digit), then 15 / 10 = 1
1 % 10 = 1 (first digit), then 1 / 10 = 0 → stop

We cube each extracted digit and accumulate the sum. If the sum matches the original number, it is an Armstrong number.

Since the constraint limits n to 3-digit numbers, the power is always 3. However, we will write a generalized solution that first counts the digits (computes the order) and raises each digit to that power. This makes the code correct for Armstrong numbers of any length.

Step-by-Step Explanation

Let's trace through with n = 153:

Step 1 — Count the digits: Starting with 153, divide by 10 repeatedly: 153 → 15 → 1 → 0. We divided 3 times, so the order k = 3.

Step 2 — Initialize: Set sum = 0, and keep a copy temp = 153 (we need the original value for comparison later).

Step 3 — Extract digit 3: temp = 153, digit = 153 % 10 = 3. Compute 3³ = 27. Add to sum: sum = 0 + 27 = 27. Update temp = 153 / 10 = 15.

Step 4 — Extract digit 5: temp = 15, digit = 15 % 10 = 5. Compute 5³ = 125. Add to sum: sum = 27 + 125 = 152. Update temp = 15 / 10 = 1.

Step 5 — Extract digit 1: temp = 1, digit = 1 % 10 = 1. Compute 1³ = 1. Add to sum: sum = 152 + 1 = 153. Update temp = 1 / 10 = 0.

Step 6 — temp is 0, loop ends. Compare: sum (153) == n (153)? Yes! → 153 is an Armstrong number.

Armstrong Number Check — Extracting Digits and Computing Sum of Cubes — Watch as we extract each digit of 153, cube it, and accumulate the sum. At the end, we compare the sum with the original number to determine if it's Armstrong.

Now let's trace a non-Armstrong number, n = 372:

Step 1: Order = 3 (three digits).

Step 2: sum = 0, temp = 372.

Step 3: digit = 372 % 10 = 2. 2³ = 8. sum = 0 + 8 = 8. temp = 37.

Step 4: digit = 37 % 10 = 7. 7³ = 343. sum = 8 + 343 = 351. temp = 3.

Step 5: digit = 3 % 10 = 3. 3³ = 27. sum = 351 + 27 = 378. temp = 0.

Step 6: sum (378) ≠ n (372) → Not an Armstrong number.

Notice how close 372 is to being Armstrong — the sum 378 is only 6 away! But close does not count; the match must be exact.

Algorithm

Count digits: Set order = 0, copy temp = n. While temp > 0, increment order and set temp = temp / 10.
Compute sum of powers: Reset temp = n, sum = 0. While temp > 0:
- Extract digit: digit = temp % 10
- Add digit^order to sum
- Remove digit: temp = temp / 10
Compare: If sum == n, return true. Else return false.

Code

#include <iostream>
#include <cmath>
using namespace std;

class Solution {
public:
    bool isArmstrong(int n) {
        // Step 1: Count the number of digits
        int order = 0;
        int temp = n;
        while (temp > 0) {
            order++;
            temp /= 10;
        }
        
        // Step 2: Compute sum of each digit
        //         raised to the power of order
        temp = n;
        int sum = 0;
        while (temp > 0) {
            int digit = temp % 10;
            sum += pow(digit, order);
            temp /= 10;
        }
        
        // Step 3: Compare
        return sum == n;
    }
};

class Solution:
    def isArmstrong(self, n: int) -> bool:
        # Step 1: Count the number of digits
        order = 0
        temp = n
        while temp > 0:
            order += 1
            temp //= 10
        
        # Step 2: Compute sum of each digit
        #         raised to the power of order
        temp = n
        total = 0
        while temp > 0:
            digit = temp % 10
            total += digit ** order
            temp //= 10
        
        # Step 3: Compare
        return total == n

class Solution {
    public boolean isArmstrong(int n) {
        // Step 1: Count the number of digits
        int order = 0;
        int temp = n;
        while (temp > 0) {
            order++;
            temp /= 10;
        }
        
        // Step 2: Compute sum of each digit
        //         raised to the power of order
        temp = n;
        int sum = 0;
        while (temp > 0) {
            int digit = temp % 10;
            sum += (int) Math.pow(digit, order);
            temp /= 10;
        }
        
        // Step 3: Compare
        return sum == n;
    }
}

Complexity Analysis

Time Complexity: O(d × log d), where d is the number of digits in n.

We iterate through the digits twice: once to count them (O(d)) and once to compute the sum (O(d)). Computing digit^order via exponentiation by squaring takes O(log d) per digit. Total: O(d × log d).

For the given constraint (100 ≤ n < 1000), d = 3, so this is effectively O(1) — constant time.

Space Complexity: O(1)

We only use a fixed number of integer variables regardless of input size.

Why This Approach Is Not Efficient

For this specific problem (3-digit numbers), the brute force approach is already very efficient — it runs in constant time. However, if we consider the generalized problem for larger numbers, there are two areas of improvement:

Redundant power computations: In the brute force, we call pow(digit, order) for every digit independently. If the same digit appears multiple times (e.g., 9474 has two 4s), we recompute the same power. For a number with many repeated digits, precomputing digit powers in a lookup table avoids redundant work.
Two passes over the number: We traverse the digits twice — once to count them and once to compute the sum. By converting the number to a string, we can get both the digit count and easy digit access in a single, clean operation.

The next approach addresses both issues using string conversion.

Optimal Approach - String Conversion with Precomputed Powers

Intuition

Instead of extracting digits with modulus and division, we can convert the number to a string. This gives us two immediate benefits:

Instant digit count: The string length is the number of digits — no counting loop needed.
Clean digit access: Each character in the string is a digit. Converting a character to its numeric value is straightforward: char - '0' in C++/Java, or int(char) in Python.

Additionally, we can precompute a power table: for each digit 0-9, calculate digit^k once and store it. Then for each digit in the number, we simply look up the precomputed value. This avoids redundant exponentiation when digits repeat.

For the constrained version (3-digit numbers), both approaches run in constant time. But the string-based approach is cleaner, less error-prone, and scales better to the general case. It eliminates the two-pass logic of the brute force and avoids potential integer overflow issues from repeated multiplication.

Step-by-Step Explanation

Let's trace through with n = 153:

Step 1 — Convert to string: "153". Length = 3, so k = 3.

Step 2 — Precompute power table for k = 3:

Digit	0	1	2	3	4	5	6	7	8	9
d³	0	1	8	27	64	125	216	343	512	729

Step 3 — Look up and sum:

Digit '1' → table[1] = 1
Digit '5' → table[5] = 125
Digit '3' → table[3] = 27
Sum = 1 + 125 + 27 = 153

Step 4 — Compare: 153 == 153? Yes → Armstrong number!

Notice how each digit lookup is O(1) — no repeated multiplication needed.

String-Based Armstrong Check with Power Lookup Table — See how converting to a string gives instant digit access, and a precomputed power table makes each digit's contribution a simple O(1) lookup.

Algorithm

Convert n to a string s.
Set k = length of s (number of digits).
(Optional optimization) Precompute power_table[d] = d^k for d = 0 to 9.
Initialize sum = 0.
For each character c in s:
- Convert to digit: d = c - '0'
- Add power_table[d] to sum
Return sum == n.

Code

#include <iostream>
#include <string>
#include <cmath>
using namespace std;

class Solution {
public:
    bool isArmstrong(int n) {
        string s = to_string(n);
        int k = s.length();
        
        // Precompute power table
        int power[10];
        for (int d = 0; d < 10; d++) {
            power[d] = (int)pow(d, k);
        }
        
        // Sum using lookup
        int sum = 0;
        for (char c : s) {
            sum += power[c - '0'];
        }
        
        return sum == n;
    }
};

class Solution:
    def isArmstrong(self, n: int) -> bool:
        s = str(n)
        k = len(s)
        
        # Precompute power table
        power = [d ** k for d in range(10)]
        
        # Sum using lookup
        total = sum(power[int(c)] for c in s)
        
        return total == n

class Solution {
    public boolean isArmstrong(int n) {
        String s = Integer.toString(n);
        int k = s.length();
        
        // Precompute power table
        int[] power = new int[10];
        for (int d = 0; d < 10; d++) {
            power[d] = (int) Math.pow(d, k);
        }
        
        // Sum using lookup
        int sum = 0;
        for (char c : s.toCharArray()) {
            sum += power[c - '0'];
        }
        
        return sum == n;
    }
}

Complexity Analysis

Time Complexity: O(d), where d is the number of digits in n.

Precomputing the power table takes O(10 × log d) = O(log d) since we compute 10 powers each via O(log d) exponentiation. Summing the digit powers takes O(d) with O(1) lookups. Total: O(d + log d) = O(d).

For the given constraint (3-digit numbers), this is O(1).

Space Complexity: O(d) for the string representation, plus O(10) = O(1) for the power table.

Overall: O(d) for the string, which is O(1) for 3-digit numbers.

Comparison with Brute Force:

Aspect	Brute Force	Optimal (String + Table)
Digit counting	Separate loop	String length
Power computation	Per digit, may repeat	Precomputed once
Code clarity	Modulus/division logic	Clean string iteration
Passes over number	Two (count + sum)	One (after conversion)