Check If a Number Is an Armstrong Number

52.6k
0

Given an integer N, determine whether it is an Armstrong number or not. Return true if it is an Armstrong number, otherwise return false.

An Armstrong number, also known as a Narcissistic number, is a number that is equal to the sum of its own digits, where each digit is raised to the power of the total number of digits.

Example 1

Input: n = 153

Output: true

Explanation: 153 has 3 digits, and 1^3 + 5^3 + 3^3 = 1 + 125 + 27 = 153, so it is an Armstrong number.

Example 2

Input: n = 123

Output: false

Explanation: 123 has 3 digits, and 1^3 + 2^3 + 3^3 = 1 + 8 + 27 = 36, which is not equal to 123.

Approach

The first observation is the one given directly by the definition: the answer depends only on the digits of the number and on how many digits the number has. So before anything else, the number of digits must be known.

Once that count is available, the rest of the idea becomes natural. Pick each digit one by one, raise it to that digit count, keep adding the result, and finally check whether the total comes back to the original number. If it does, the number is Armstrong. If it does not, it is not.

Algorithm

  • First, handle the negative case by returning false, because Armstrong numbers are defined for positive numbers and, in practice, the usual beginner version also includes 0 as a valid Armstrong number.

  • Keep a copy of the original number, because the number will be broken apart digit by digit during processing, but the final comparison must still be made with the original value.

  • Count how many digits are present in the number. This count matters because every digit must be raised to exactly that power.

  • Extract digits one by one using % 10, raise each digit to the power of the digit count, and keep adding those values to a running sum. This step builds exactly the quantity described in the problem definition.

  • After all digits have been processed, compare the final sum with the original number. If both values are equal, return true; otherwise, return false.

Key Points

  • Negative numbers are not Armstrong numbers in the usual DSA definition.

  • 0 is considered an Armstrong number because it has one digit and 0^1 = 0.

  • Every single-digit non-negative number is an Armstrong number.

Dry Run

Armstrong Number Dry Run

Armstrong Number Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*
Returns true if n is an Armstrong Number
by summing each digit raised to the digit count.
*/
bool isArmstrong(int n) {
// Negative numbers are not Armstrong numbers.
if (n < 0) {
return false;
}
// Stores the original value for the final comparison.
int original = n;
// The number 0 has exactly one digit.
int digits = (n == 0) ? 1 : 0;
int temp = n;
// Count how many digits are present in the number.
while (temp > 0) {
digits++;
temp /= 10;
}
// Reset temp so the digits can now be processed one by one.
temp = n;
// Stores the sum built from digit powers.
int sum = 0;
// Handle 0 directly because its digit extraction loop would not run.
if (temp == 0) {
sum = 0;
}
while (temp > 0) {
// Extract the current last digit.
int digit = temp % 10;
// Build digit^digits using integer multiplication.
int powerValue = 1;
for (int i = 0; i < digits; i++) {
powerValue *= digit;
}
// Add the current digit contribution to the total sum.
sum += powerValue;
temp /= 10;
}
// Compare the computed digit-power sum with the original number.
return sum == original;
}
};
// Driver code starts
int main() {
int n = 153;
Solution obj;
cout << (obj.isArmstrong(n) ? "true" : "false") << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(d * k), where d is the number of digits and k is the digit count used as the power, because each digit is processed once and each power is computed over k multiplications in this implementation.

Space Complexity: O(1), because only a few variables are used.

Optimal Approach

The core idea of Armstrong Number does not change: every digit must be raised to the power of the number of digits.

However, we can compute the same power much faster using Fast Exponentiation (Binary Exponentiation). Instead of multiplying one by one, it repeatedly squares the current value and uses the binary representation of the exponent to decide which powers to include. Since the exponent is roughly halved in every step, the number of operations reduces from O(p) to O(log p).

Algorithm

  • If the number is negative, return false because Armstrong numbers are usually considered for non-negative integers.

  • If the number is 0, treat it as a 1-digit Armstrong number.

  • Count how many digits are present in the number.

  • Traverse each digit one by one using modulus and division.

  • For every digit, calculate digit^count using fast exponentiation.

    • Initialize result = 1 and base = 1.

    • While the exponent is greater than 0:

      • If the exponent is odd, multiply result by the current base.

      • Square the base (base = base × base) so it represents the next power of two.

      • Divide the exponent by 2 (ignore the remainder), effectively processing its binary representation one bit at a time.

    • When the exponent becomes 0, result contains digit^count.

  • Add all these powered values into a sum.

  • If the final sum becomes equal to the original number, return true. Otherwise, return false.

Dry Run

Armstrong Number Optimal Dry Run

Armstrong Number Optimal Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*
Checks whether the given number is an Armstrong number.
*/
bool isArmstrong(int n) {
// Negative numbers are not considered Armstrong numbers here.
if (n < 0) {
return false;
}
// Zero is a valid Armstrong number.
if (n == 0) {
return true;
}
int original = n;
// This stores how many digits are present in the number.
int digits = countDigits(n);
// This variable stores the sum of powered digits.
int sum = 0;
while (n > 0) {
int digit = n % 10;
sum += fastPower(digit, digits);
n /= 10;
}
// The number is Armstrong only if the computed sum matches the original value.
return sum == original;
}
private:
int countDigits(int n) {
int count = 0;
while (n > 0) {
count++;
n /= 10;
}
return count;
}
int fastPower(int base, int exponent) {
int result = 1;
while (exponent > 0) {
// If the current bit is set, include the current base in the answer.
if (exponent & 1) {
result *= base;
}
base *= base;
exponent >>= 1;
}
return result;
}
};
// Driver code starts
int main() {
Solution sol;
int n = 9474;
if (sol.isArmstrong(n)) {
cout << "true\n";
} else {
cout << "false\n";
}
return 0;
}

Complexity Analysis

Time Complexity: O(d log d), where d is the number of digits. There are d digits, and each power calculation takes O(log d) time and d = log10 N.

Space Complexity: O(1) because constant space is used.

Interview follow-up Questions

Yes. It is a single-digit number, and 0^1 = 0, so it satisfies the condition.

MathsIntroduction to DSA

Read Similar Blogs

Two PointerSortingMathsBinary SearchArrays

Find the Smallest Divisor Given a Threshold

Given an integer array nums and an integer threshold , find the smallest positive integer divisor such that: After dividing every element of nums by divisor , rounding each result up, and adding al...

84.2k
Two PointerSortingMathsBinary SearchArrays

Book Allocation Problem: Allocate Minimum Pages

Given an array pages , where pages[i] represents the number of pages in the i-th book, and an integer students , allocate all books among the students. The allocation must follow thes...

63.2k
Two PointerBinary SearchGreedyMathsArrays

Aggressive Cows: Maximize the Minimum Distance

cpp #include using namespace std; class Solution { public: /* Checks if all cows can be placed while keeping at least distance gap between every pair. */ bool canPlace(vector & stalls, int k, int d...

102k
Comments0