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:

1. Create an array $F$ of length $10$ containing the frequencies of the digits in $N$
2. Calculate $\dot N = (F[0] \times pow(0,n)) + (F[1] \times pow(1,n))+ … (F[9] \times pow(9,n))$
3. 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$.