Coding interview question: Determine if number is an Armstrong number
Problem statement
In this article we will be discussing another (see the previous article counting triples with a given sum) of the most common coding interview questions. The problem statement is really simple and goes as follows:
Given an positive integer
N
determine if it is an Armstrong number?
A number $x_1x_2…x_n$ (1 \leq x_i \leq 9 $ is a digit ) of length $n$ is an Armstrong number if the following is true:
$x_nx_{n-1}…x_2x_1 = pow(x_1,n) + pow(x_2,n) + … pow(x_n,n)$
In other words if raising all digits to power $n$ and sum all them up you obtain the original number, then $N$ is an Armstrong number.
Example
Input : N = 8208 Output : true => pow(8,4) + pow(0,4) + pow(2,4) + pow(8,4) = 8208
Input : 407 Output : true => pow(7,3) + pow(0,3) + pow(4,3) = 407
Input : 24 Output : false => pow(4,2) + pow(2,2) = 20 != 24

Solution
We start by noticing that in $pow(x,n)$
- $1 \leq x \leq 9 $
- $ n $: never changes
- If the digit $d$ appears $l$ times in the numbers, then the term $pow(d,n)$ will appear $l$ times.
The approach will be using is the following:
- Create an array $F$ of length $10$ containing the frequencies of the digits in $N$
- Calculate $\dot N = (F[0] \times pow(0,n)) + (F[1] \times pow(1,n))+ … (F[9] \times pow(9,n))$
- If $N = \dot N$ return true, false otherwise
C++ code
The idea above can be coded as follows:
bool is_armstrong(const int N) { //calculate frequency of digits //and length of N array<int, 10> F = {0}; int n = 0; for(int _N = N ; _N ; _N/=10){ F[_N%10]++; n++; } int N1 = 0; for(int i = 0 ; i < 10 ; i++) N1 += F[i] * pow(i,n); return N1==N; }
The time complexity of the code above is linear in the number of digits of $N$. The space complexity is constant.
This mean that in terms of $N$ the time complexity is $O(log(N))$. There are at most $log_{10}(N)$ digits in $N$.
You can try the above code online on Wandbox.
In this article we discussed a common coding interview question asked by many tech companies. The takeaways from this exercises are:
- $N \mod 10$ will return you the last digit of $N$
- The number of digits of $N$ is given by the number of times you can divide it by $10$ before obtaining $0$.