Armstrong Number in C++

Armstrong Number in C++ (also known as a Narcissistic Number or Pluperfect Digital Invariant) is a classic number theory and digit-manipulation problem tested in technical interviews and programming assessments at companies like Amazon, TCS, Microsoft, and Infosys. An Armstrong Number of K digits is defined as a non-negative integer that equals the sum of its own digits each raised to the power of K. In this comprehensive masterclass, we will trace the complete algorithmic evolution: starting from a naive String Conversion method, identifying the dangerous IEEE-754 floating-point truncation trap with std::pow, advancing through Pure Integer Modulo Extraction, and engineering an Optimal Lookup-Table Accelerated Digit Accumulator. We will also benchmark all approaches across 10,000,000 integers, explore range generation, and provide “Try it yourself” challenges after every section.

🔹 What is an Armstrong Number? Mathematical Definition & Invariants

Mathematically, a non-negative integer N with K digits is an Armstrong number if and only if:

N = d₁ᴷ + d₂ᴷ + d₃ᴷ + ... + dₖᴷ
where:
  K = Number of digits = ⌊log₁₀ N⌋ + 1
  dᵢ = Individual base-10 digits of N

Let’s walk through concrete examples with varying digit counts K:

• Single-Digit Numbers (K = 1):
  • 7¹ = 7 (True → All single-digit integers 0 to 9 are trivially Armstrong numbers).
• 3-Digit Numbers (K = 3):
  • 153: 1³ + 5³ + 3³ = 1 + 125 + 27 = 153 (True → Armstrong!).
  • 370: 3³ + 7³ + 0³ = 27 + 343 + 0 = 370 (True → Armstrong!).
  • 371: 3³ + 7³ + 1³ = 27 + 343 + 1 = 371 (True → Armstrong!).
  • 407: 4³ + 0³ + 7³ = 64 + 0 + 343 = 407 (True → Armstrong!).
  • 123: 1³ + 2³ + 3³ = 1 + 8 + 27 = 36 != 123 (False).
• 4-Digit Numbers (K = 4):
  • 1634: 1⁴ + 6⁴ + 3⁴ + 4⁴ = 1 + 1296 + 81 + 256 = 1634 (True → Armstrong!).
  • 8208: 8⁴ + 2⁴ + 0⁴ + 8⁴ = 4096 + 16 + 0 + 4096 = 8208 (True → Armstrong!).
  • 9474: 9⁴ + 4⁴ + 7⁴ + 4⁴ = 6561 + 256 + 2401 + 256 = 9474 (True → Armstrong!).

Try it yourself

• Are there any 2-digit Armstrong numbers (in range 10 to 99)? (Hint: Test 10 to 99 with d₁² + d₂²).
• Verify whether 54748 is a 5-digit Armstrong number by computing 5⁵ + 4⁵ + 7⁵ + 4⁵ + 8⁵.

🔹 Approach 1: Brute Force (String Conversion & std::pow)

Intuition & Reasoning: A beginner friendly way to process digits is to convert the integer into an std::string using std::to_string(n). The string length immediately gives the digit count K (str.length()). We then iterate over each character, convert the ASCII char back to an integer (c - '0'), and add std::pow(digit, K) to a running sum.

#include <iostream>
#include <string>
#include <cmath>

using namespace std;

// Brute Force: String conversion + std::pow
bool is_armstrong_string(int n) {
    if (n < 0) return false; // Negative numbers cannot be Armstrong numbers

    string s = to_string(n);
    int k = static_cast<int>(s.length());
    long long sum = 0;

    for (char c : s) {
        int digit = c - '0';
        sum += static_cast<long long>(round(pow(digit, k)));
    }

    return sum == n;
}

int main() {
    int test1 = 153;
    int test2 = 1634;
    int test3 = 123;

    cout << "--- Brute Force String Conversion ---\n";
    cout << test1 << " is Armstrong: " << (is_armstrong_string(test1) ? "True" : "False") << " (Expected: True)\n";
    cout << test2 << " is Armstrong: " << (is_armstrong_string(test2) ? "True" : "False") << " (Expected: True)\n";
    cout << test3 << " is Armstrong: " << (is_armstrong_string(test3) ? "True" : "False") << " (Expected: False)\n";
    return 0;
}

Output

--- Brute Force String Conversion ---
153 is Armstrong: True (Expected: True)
1634 is Armstrong: True (Expected: True)
123 is Armstrong: False (Expected: False)

Takeaway: The string approach works correctly, but incurs unnecessary heap memory allocation for the temporary string and relies on floating-point arithmetic.

Complexity Analysis & The Bottleneck:

• Time Complexity (TC): O(K) = O(log₁₀ N): Formatting into a string takes K steps, and the loop processes K characters. Since K ≤ 10 for standard 32-bit integers, runtime is small.
• Space Complexity (SC): O(K): Allocates dynamic heap memory for the std::string object.
• The Inefficiency:
  • Heap allocation and string destruction overhead on every function invocation.
  • Invoking std::pow triggers software floating-point emulation or SSE vector register conversions with potential rounding inaccuracies.

Try it yourself

• What happens if you omit round() and write sum += (int)pow(digit, k)? (Read the next section to discover the IEEE-754 precision bug!).
• Trace what to_string(0) produces and verify that 0 is correctly evaluated as an Armstrong number.

🔹 The Dangerous IEEE-754 Floating-Point Precision Bug with std::pow

One of the most insidious bugs in C++ number theory questions is blindly casting std::pow() directly to an integer:

// SILENT BUG IN PRODUCTION!
int digit = 5, k = 3;
int result = (int)pow(digit, k); // Might evaluate to 124 instead of 125!

Why does this happen?

• std::pow(double, double) is a floating-point algorithm computed via logarithmic approximations: e^(k * ln(digit)).
• Due to binary floating-point rounding under the IEEE-754 standard, pow(5, 3) can yield 124.99999999999999.
• When static-cast to int, C++ truncates the fractional part towards zero, turning 124.999999 into 124!
• The Golden Rule: NEVER use floating-point std::pow for exact integer arithmetic in C++. Always write an integer power function or use a precomputed lookup table.

Try it yourself

• Test (int)pow(10, 2) on different compilers (GCC vs Clang vs MSVC) without optimization flags to observe floating-point truncation.
• Write an exact integer power function long long integer_pow(int base, int exp) using a simple loop.

🔹 Approach 2: Better (Two-Pass Integer Modulo Extraction)

Optimization Intuition: We eliminate heap allocations completely by extracting digits mathematically using modulo arithmetic (n % 10) and integer division (n / 10):

• Pass 1 (Count Digits): Repeatedly divide a copy of N by 10 to count the total number of digits K.
• Pass 2 (Extract & Accumulate): Extract the last digit d = temp % 10, compute dᴷ with exact integer multiplication, add it to sum, and divide temp /= 10.

#include <iostream>

using namespace std;

// Exact integer exponentiation (Zero floating-point inaccuracies)
long long int_power(int base, int exp) {
    long long res = 1;
    for (int i = 0; i < exp; ++i) {
        res *= base;
    }
    return res;
}

// Better: Two-Pass Pure Integer Modulo
bool is_armstrong_integer(int n) {
    if (n < 0) return false;
    if (n == 0) return true; // 0^1 = 0

    // Step 1: Count total number of digits (K)
    int k = 0;
    int temp = n;
    while (temp > 0) {
        ++k;
        temp /= 10;
    }

    // Step 2: Accumulate digit powers
    long long sum = 0;
    temp = n;
    while (temp > 0) {
        int digit = temp % 10;
        sum += int_power(digit, k);
        temp /= 10;
    }

    return sum == n;
}

int main() {
    int test1 = 371;
    int test2 = 9474;
    int test3 = 500;

    cout << "--- Two-Pass Integer Modulo ---\n";
    cout << test1 << " is Armstrong: " << (is_armstrong_integer(test1) ? "True" : "False") << " (Expected: True)\n";
    cout << test2 << " is Armstrong: " << (is_armstrong_integer(test2) ? "True" : "False") << " (Expected: True)\n";
    cout << test3 << " is Armstrong: " << (is_armstrong_integer(test3) ? "True" : "False") << " (Expected: False)\n";
    return 0;
}

Output

--- Two-Pass Integer Modulo ---
371 is Armstrong: True (Expected: True)
9474 is Armstrong: True (Expected: True)
500 is Armstrong: False (Expected: False)

Takeaway: Two-Pass integer extraction operates in O(1) auxiliary memory with guaranteed integer precision, completely eliminating dynamic string allocations and floating-point errors.

Step by Step Dry Run (N = 153):

Pass 1: Digit Count (temp = 153)
- 153 / 10 = 15 -> k = 1
-  15 / 10 = 1  -> k = 2
-   1 / 10 = 0  -> k = 3 -> Total Digits K = 3

Pass 2: Accumulate (temp = 153, sum = 0)
- Iteration 1: digit = 153 % 10 = 3 -> sum += 3³ = 27  -> temp = 15
- Iteration 2: digit =  15 % 10 = 5 -> sum += 5³ = 125 -> sum = 152 -> temp = 1
- Iteration 3: digit =   1 % 10 = 1 -> sum += 1³ = 1   -> sum = 153 -> temp = 0

Final Comparison: sum (153) == N (153) -> Returns True!

Complexity Analysis & Limitations:

• Time Complexity (TC): O(K) = O(log₁₀ N): Pass 1 performs K divisions; Pass 2 performs K modulo extractions with K × K multiplications. Total operations ≤ 30 instructions for a 32-bit integer.
• Space Complexity (SC): O(1): Uses primitive stack variables with zero memory overhead.
• The Remaining Inefficiency: When evaluating whether repeated digits appear (e.g. in 9474 where 4 appears twice), we recompute 4⁴ multiple times. Furthermore, in high throughput loops checking millions of numbers, computing powers repeatedly adds instruction cycles.

Try it yourself

• Why is it essential to save temp = n before running the while loop? What happens if you modify n directly?
• Trace what happens for n = 0. Why is an explicit base check helpful?

🔹 Approach 3: Optimal (Precomputed Digit Power Table & Early Exit)

The Core Systems Insight (Lookup Table Acceleration): Since any base-10 digit can only take values from 0 to 9, once we determine the digit count K, there are only 10 possible power values: 0ᴷ, 1ᴷ, 2ᴷ, …, 9ᴷ!

Instead of executing multiplication loops inside the digit extraction pass, we can precompute a 10-element lookup array on the CPU stack: powers[10] = {0ᴷ, 1ᴷ, 2ᴷ, ..., 9ᴷ}. Then, digit power accumulation becomes an instant O(1) L1 Cache Array Indexing operation (sum += powers[digit])!

For K = 3:
  powers[0] = 0,   powers[1] = 1,   powers[2] = 8,   powers[3] = 27
  powers[4] = 64,  powers[5] = 125, powers[6] = 216, powers[7] = 343
  powers[8] = 512, powers[9] = 729

For N = 153:
  sum = powers[3] + powers[5] + powers[1]
      = 27 + 125 + 1 = 153 (Executed with zero multiplication instructions!)

Additionally, we introduce an Early Exit Optimization: if sum > n at any point during accumulation, we immediately break out of the loop and return false!

#include <iostream>
#include <vector>
#include <array>

using namespace std;

// Optimal: Precomputed Digit Power Lookup Table + Early Exit
bool is_armstrong_optimal(long long n) {
    if (n < 0) return false;
    if (n < 10) return true; // Single digits 0-9 are always Armstrong numbers

    // Step 1: Count digits (K)
    int k = 0;
    long long temp = n;
    while (temp > 0) {
        ++k;
        temp /= 10;
    }

    // Step 2: Precompute 0^K through 9^K on the stack (10 elements)
    array<long long, 10> powers;
    powers[0] = 0;
    powers[1] = 1;
    for (int d = 2; d < 10; ++d) {
        long long val = 1;
        for (int p = 0; p < k; ++p) {
            val *= d;
        }
        powers[d] = val;
    }

    // Step 3: Accumulate with O(1) table lookups and early exit
    long long sum = 0;
    temp = n;
    while (temp > 0) {
        int digit = static_cast<int>(temp % 10);
        sum += powers[digit];

        // Early Exit: If sum already exceeds n, it can never equal n!
        if (sum > n) {
            return false;
        }

        temp /= 10;
    }

    return sum == n;
}

int main() {
    vector<long long> test_cases = {153, 370, 371, 407, 1634, 8208, 9474, 54748, 123, 999};

    cout << "--- Optimal Precomputed Armstrong Checker ---\n";
    for (long long num : test_cases) {
        cout << "Number: " << num << " -> " 
             << (is_armstrong_optimal(num) ? "Armstrong" : "Not Armstrong") << "\n";
    }
    return 0;
}

Output

--- Optimal Precomputed Armstrong Checker ---
Number: 153 -> Armstrong
Number: 370 -> Armstrong
Number: 371 -> Armstrong
Number: 407 -> Armstrong
Number: 1634 -> Armstrong
Number: 8208 -> Armstrong
Number: 9474 -> Armstrong
Number: 54748 -> Armstrong
Number: 123 -> Not Armstrong
Number: 999 -> Not Armstrong

Takeaway: Precomputing the 10 digit powers turns every step into a direct array lookup and enables early exit when the sum overflows N.

Complexity Analysis (Proof of Optimum):

• Time Complexity (TC): O(K) = O(log₁₀ N):
  • Pass 1 (Digit count): K divisions.
  • Precomputing 10 powers: Fixed 10 × K multiplications → O(K).
  • Pass 2 (Accumulation): At most K table lookups and additions.
  • Total TC = O(K) (executing in ~15 nanoseconds).
• Space Complexity (SC): O(1): Exactly 10 long long integers allocated in CPU L1 stack memory (80 bytes).

Try it yourself

• Trace how the Early Exit condition if (sum > n) return false; terminates early on N = 999 (since 9³ = 729, after two digits 729 + 729 = 1458 > 999).
• How would you modify the function to check 64-bit numbers with up to 19 digits?

🔹 Range Query: Printing All Armstrong Numbers in Range [1..M]

A frequent interview variant asks: “Print all Armstrong numbers between 1 and M” (e.g. M = 100,000).

#include <iostream>
#include <vector>

using namespace std;

// Print all Armstrong numbers up to limit M
vector<long long> find_armstrong_in_range(long long low, long long high) {
    vector<long long> results;
    for (long long i = low; i <= high; ++i) {
        if (is_armstrong_optimal(i)) {
            results.push_back(i);
        }
    }
    return results;
}

int main() {
    long long limit = 10000;
    cout << "--- Armstrong Numbers in Range [1..10000] ---\n";
    auto armstrongs = find_armstrong_in_range(1, limit);
    for (long long x : armstrongs) {
        cout << x << " ";
    }
    cout << "\n";
    return 0;
}

Output

--- Armstrong Numbers in Range [1..10000] ---
1 2 3 4 5 6 7 8 9 153 370 371 407 1634 8208 9474 

🔹 Lab: High Throughput Performance Benchmark (10,000,000 Numbers)

Let’s benchmark our three checker strategies by evaluating all integers from 1 to 10,000,000 to measure total execution time and throughput in Million evaluations per second.

#include <iostream>
#include <vector>
#include <chrono>
#include <string>
#include <cmath>
#include <iomanip>

using namespace std;

// 1. String conversion
bool bench_string(int n) {
    string s = to_string(n);
    int k = static_cast<int>(s.length());
    long long sum = 0;
    for (char c : s) sum += static_cast<long long>(round(pow(c - '0', k)));
    return sum == n;
}

// 2. Pure Integer Modulo (Loop multiplication)
bool bench_integer(int n) {
    if (n < 10) return true;
    int k = 0, temp = n;
    while (temp > 0) { ++k; temp /= 10; }
    long long sum = 0;
    temp = n;
    while (temp > 0) {
        int d = temp % 10;
        long long p = 1;
        for (int i = 0; i < k; ++i) p *= d;
        sum += p;
        temp /= 10;
    }
    return sum == n;
}

// 3. Optimal Precomputed Table + Early Exit
bool bench_optimal(int n) {
    if (n < 10) return true;
    int k = 0, temp = n;
    while (temp > 0) { ++k; temp /= 10; }
    long long powers[10];
    powers[0] = 0; powers[1] = 1;
    for (int d = 2; d < 10; ++d) {
        long long p = 1;
        for (int i = 0; i < k; ++i) p *= d;
        powers[d] = p;
    }
    long long sum = 0;
    temp = n;
    while (temp > 0) {
        sum += powers[temp % 10];
        if (sum > n) return false;
        temp /= 10;
    }
    return sum == n;
}

int main() {
    constexpr int N = 10000000; // 10 Million numbers

    cout << "--- CppMonk Armstrong Benchmark Lab ---\n";
    cout << "Evaluating " << N << " integers...\n\n";

    // Benchmark 1: String Conversion
    {
        auto start = chrono::high_resolution_clock::now();
        int count = 0;
        for (int i = 1; i <= N; ++i) if (bench_string(i)) ++count;
        auto end = chrono::high_resolution_clock::now();
        double ms = chrono::duration_cast<chrono::milliseconds>(end - start).count();
        cout << fixed << setprecision(2);
        cout << "1. String + std::pow:           " << ms << " ms (" << ((N / ms) / 1000.0) << " M nums/sec)\n";
    }

    // Benchmark 2: Integer Modulo
    {
        auto start = chrono::high_resolution_clock::now();
        int count = 0;
        for (int i = 1; i <= N; ++i) if (bench_integer(i)) ++count;
        auto end = chrono::high_resolution_clock::now();
        double ms = chrono::duration_cast<chrono::milliseconds>(end - start).count();
        cout << "2. Pure Integer Modulo:         " << ms << " ms (" << ((N / ms) / 1000.0) << " M nums/sec)\n";
    }

    // Benchmark 3: Optimal Table + Early Exit
    {
        auto start = chrono::high_resolution_clock::now();
        int count = 0;
        for (int i = 1; i <= N; ++i) if (bench_optimal(i)) ++count;
        auto end = chrono::high_resolution_clock::now();
        double ms = chrono::duration_cast<chrono::milliseconds>(end - start).count();
        cout << "3. Optimal Table + Early Exit:  " << ms << " ms (" << ((N / ms) / 1000.0) << " M nums/sec)\n";
    }

    return 0;
}

Output

--- CppMonk Armstrong Benchmark Lab ---
Evaluating 10000000 integers...

1. String + std::pow:           1482.00 ms (6.75 M nums/sec)
2. Pure Integer Modulo:         384.00 ms (26.04 M nums/sec)
3. Optimal Table + Early Exit:  128.00 ms (78.12 M nums/sec)

Takeaway: Precomputing digit powers and enabling early exits processes over 78.1 Million numbers per second, delivering an 11.5x speedup over string conversion and a 3x speedup over naive integer modulo loops!

Try it yourself

• Compile the benchmark with -O3 -march=native and observe how the compiler unrolls the digit division loops.
• Why does early exit provide such a massive speedup on 10,000,000 numbers? (Hint: The vast majority of random integers exceed N after just 1 or 2 high-power digit additions!).

🔹 Key Pitfalls & Common Interview Traps

• Trap 1: Hardcoding Digit Power to 3: A classic candidate mistake is assuming all Armstrong numbers have 3 digits (e.g. writing d*d*d). This causes the code to fail for 4-digit numbers like 1634 or 5-digit numbers like 54748. Always calculate K dynamically.
• Trap 2: Casting Floating-Point std::pow directly to int: As proven earlier, (int)pow(5, 3) can truncate to 124. Always use integer arithmetic.
• Trap 3: Mutating the Input Parameter without Saving a Copy: Writing while (n > 0) { ... n /= 10; } return sum == n; compares sum against 0 because n was mutated to 0! Always declare temp = n.
• Trap 4: Missing Single-Digit Armstrong Numbers: Single digits 0 through 9 are valid Armstrong numbers (d¹ = d). Ensure your base cases handle them gracefully.

Try it yourself

• Write a test case for N = 0 and verify that your function returns true.
• Verify why negative numbers (e.g. -153) are mathematically rejected before running the modulo loop.

🔹 Comparison of All Approaches

┌─────────────────────────────────────┬──────────────────┬──────────────────┬────────────────────────┐
│ Approach                            │ Time Complexity  │ Space Complexity │ Precision & Safety     │
├─────────────────────────────────────┼──────────────────┼──────────────────┼────────────────────────┤
│ 1. String + std::pow                │ O(K)             │ O(K) heap        │ Prone to float bugs    │
│ 2. Two-Pass Pure Integer Modulo     │ O(K)             │ O(1)             │ 100% Exact Integer     │
│ 3. Optimal Table + Early Exit       │ O(K)             │ O(1)             │ 78M nums/sec (Fastest) │
└─────────────────────────────────────┴──────────────────┴──────────────────┴────────────────────────┘

🔹 FAQs on Armstrong Numbers in C++

Q1: What is the difference between an Armstrong number and a Palindrome number?
An Armstrong number equals the sum of its digits raised to the power of its digit count (e.g. 153 = 1³ + 5³ + 3³). A Palindrome number reads identically forward and backward (e.g. 121 or 1331).

Q2: How many Armstrong numbers exist in total in base 10?
There are exactly 88 Armstrong numbers in base 10! The largest Armstrong number has 39 digits: 115,132,219,018,763,992,565,095,597,973,971,522,401. Beyond 60 digits, K · 9ᴷ < 10^K-1, proving that no Armstrong numbers can exist beyond a finite limit.

Q3: Why is std::pow dangerous for Armstrong number calculation?
std::pow computes floating-point results. Due to IEEE-754 mantissa approximations, pow(5, 3) can evaluate to 124.999999, which truncates to 124 when cast to an integer, causing false negatives.

Q4: How do we count digits without a while loop?
You can compute the number of digits in O(1) time using the base-10 logarithm formula: int k = (n == 0) ? 1 : static_cast<int>(log10(n)) + 1;.

Q5: Are single-digit numbers considered Armstrong numbers?
Yes. Every single-digit integer from 0 to 9 is an Armstrong number because d¹ = d.

Q6: Can negative numbers be Armstrong numbers?
By standard mathematical convention, Armstrong numbers are strictly defined for non-negative integers. Negative numbers return false.

Q7: How can we prevent integer overflow for large powers like 9¹⁹?
Use 64-bit unsigned integers (uint64_t) or unsigned long long. In competitive programming, if K exceeds 19 digits, use __int128_t or custom BigInt structures.

Q8: What real world applications use digit invariant properties?
Digit invariants and digit sum hashing are used in check-digit algorithms (e.g. Luhn algorithm for credit cards, ISBN validation for books, and UPC barcode verification).

🔹 Wrapping Up

Armstrong Number in C++ is an excellent problem for mastering pure integer arithmetic, avoiding floating-point precision pitfalls, and applying lookup table optimizations. By precomputing the 10 digit powers on the stack and terminating early when running sums exceed the target, we achieve maximum instruction-level efficiency. To continue building your foundational number theory and algorithmic skills, explore our tutorials on Print All Divisors of a Number, Reverse Number in C++, and Count Digits in C++. Practice the “Try it yourself” tasks above to sharpen your coding interview problem-solving intuition!