# 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 anArmstrongnumber?

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$.

Be the first to leave a comment. Don’t be shy.