Check if a number is an Armstrong Number

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