Get this book -> Problems on Array: For Interviews and Competitive Programming

Reading time: 20 minutes | Coding time: 5 minutes

An Armstrong number is an integer such that the sum of the digits raised to the power of the number of digits is equal to the number itself. It is also known as narcissistic number. First few armstrong numbers are 0,1, 153, 370, 371 and 407.

We have presented an algorithm to check if a number is an Armstrong Number in **O(log N * loglog N)** time complexity.

## Example

Consider the number 371.Number of digits in 371 is 3.So,

```
3*3*3 + 7*7*7 + 1*1*1 =371
```

which is equal to the given number. Therefore, 371 is an armstrong number.

Now, let us consider another example 1234.Number of digits are 4.So,

```
1*1*1*1 + 2*2*2*2 + 3*3*3*3 + 4*4*4*4 = 354
```

which is not equal to the given number 1234.Therefore, 1234 is not an armstrong number.

## Algorithm

- Find the total order(number of digits) of the given number.
- For each digit d, find d raised to the power of o where o is the order calculated in Step 1.
- Compare sum of all such values with the given number.Return true if equal,false otherwise.

Pseudocode:

```
int checkArmstrong(int N)
{
int digits = order(N); // get number of digits in N
int temp = x, sum = 0;
while (temp)
{
int d = temp % 10;
sum += POWER(d, dig);
temp = temp / 10;
}
if (sum == x)
return ARMSTRONG_NUMBER;
else
return NOT_ARMSTRONG_NUMBER;
}
```

## Applications of Armstrong numbers

Armstrong numbers are used in data security.The first step is to assign a unique color for each receiver. Each color is represented with a set of three values. For example violet red color is represented in RGB format as (238, 58,140). The next step is to assign a set of three key values to each receiver.The sender is aware of the required receiver to whom the data has to be sent. So the receiverâ€™s unique color is used as the password. The set of three key values are added to the original color values and encrypted at the senderâ€™s side. This encrypted color actually acts as a password. The actual data is encrypted using Armstrong numbers.For more information regarding the application of armstrong numbers in data security,refer Data Security Using Armstrong Numbers.

## Implementations

We have provided 4 implementations (in C, C++, Java and Python).

Following is the implementation in C:

```
#include<stdio.h>
// Function to calculate x raised to the power y
int fastexp(int a, int b)
{
int res = 1;
while(b){
if(b&1) res = res*a;
b >>= 1;
a *= a;
}
return res;
}
// Function to calculate order of the number
int order(int x)
{
int n = 0;
while (x) {
n++;
x = x / 10;
}
return n;
}
/*Function to check whether the given number is
Armstrong number or not */
int checkArmstrong(int x)
{
// Calling order function
int dig = order(x);
int temp = x, sum = 0;
while (temp) {
int d = temp % 10;
sum += fastexp(d, dig);
temp = temp / 10;
}
// If satisfies Armstrong condition
if (sum == x)
return 1;
else
return 0;
}
int main()
{
int n;
printf("Enter the number:-");
scanf("%d",&n);
if(checkArmstrong(n))
printf("Armstrong\n");
else
printf("Not Armstrong\n");
}
/*
Sample Input 1:
Enter the number:-
120
Sample Output 1:
Not Armstrong
Sample Input 2:
Enter the number:-
1634
Sample Output 2:
Armstrong
*/
```

Following is the implementation in C++:

```
#include<bits/stdc++.h>
using namespace std;
/* Function to check whether the number is
an armstrong number or not. */
bool checkArmstrong(int n)
{
int dig=log10(n)+1; // Total number of digits of n
int res=0,x=n;
/* find sum of all the digits
raised to the power of the number of digits */
while(n>0)
{
res+=pow(n%10,dig);
n/=10;
}
// If satisfies Armstrong condition
if(res==x)
return true;
else
return false;
}
int main()
{
int n;
cout << "Enter the number:-"
cin >> n;
if(checkArmstrong(n))
cout << "Armstrong\n";
else
cout << "Not Armstrong\n";
}
/*
Sample Input 1:
Enter the number:-
120
Sample Output 1:
Not Armstrong
Sample Input 2:
Enter the number:-
1634
Sample Output 2:
Armstrong
*/
```

Following is the implementation in Python:

```
def fastexp(a, b):
res = 1
while(b){
if(b&1):
res = res*a
b = b>>1
a = a*a
}
return res
# Function to calculate order of the number
def order(x):
# variable to store of the number
n = 0
while (x!=0):
n = n+1
x = x/10
return n
# Function to check whether the given number is
# Armstrong number or not
def checkArmstrong (x):
dig = order(x)
temp = x
sum = 0
while (temp!=0):
d = temp%10
sum = sum + fastexp(d, dig)
temp = temp/10
# If condition satisfies
return (sum == x)
# Driver Program
print("Enter the number:-")
x = int(input())
if(checkArmstrong(x)==1):
print("Armstrong")
else:
print("Not Armstrong")
#Sample Input 1:
# Enter the number:-
# 120
#Sample Output 1:
# Not Armstrong
#Sample Input 2:
# Enter the number:-
# 1634
#Sample Output 2:
# Armstrong
```

Following is the implementation in Java:

```
import java.util.*;
public class Armstrong
{
/* Function to calculate x raised to the
power y */
int fastexp(int a, int b)
{
int res = 1;
while(b){
if(b&1) res = res*a;
b >>= 1;
a *= a;
}
return res;
}
// Function to calculate order of the number
int order(int x)
{
int n = 0;
while (x != 0)
{
n++;
x = x/10;
}
return n;
}
// Function to check whether the given number is
// Armstrong number or not
int checkArmstrong (int x)
{
// Calling order function
int dig = order(x);
int temp = x, sum = 0;
while (temp) {
int d = temp % 10;
sum += fastexp(r, dig);
temp = temp / 10;
}
// If satisfies Armstrong condition
if (sum == x)
return 1;
else
return 0;
}
// Driver Program
public static void main(String[] args)
{
Armstrong obj = new Armstrong();
Scanner scan=new Scanner(System.in);
System.out.println("Enter the number:-");
int x = scan.nextInt();
if(obj.checkArmstrong(x)==1)
System.out.println("Armstrong");
else
System.out.println("Not Armstrong");
}
}
/*
Sample Input 1:
Enter the number:-
120
Sample Output 1:
Not Armstrong
Sample Input 2:
Enter the number:-
1634
Sample Output 2:
Armstrong
*/
```

## Complexity

- Worst case time complexity:
`O(log(n))`

- Average case time complexity:
`O(log(n))`

- Best case time complexity:
`O(log(n))`

- Space complexity:
`O(1)`

The complexity is O(log N) as in a number N, there are log N digits and we are assuming power takes constant time.

In fact, raising a number M to the power K takes O(log K * log M) time.In our case, M is limited between 0 to 9 so, we can consider the overall complexity of our algorithm to be O(log N * log K) where N is the number to be checked and K is the number of digits in the number.

This results in a time complexity of **O(log N * loglog N)**.