## Microsoft student Interview Question

Students- 0of 0 votes
To generate armstrong numbers ...In O(n)..

**Country:**United States

```
#include<stdio.h>
#include<conio.h>
void armstrong(int n)
{
int i=1,k,d,s=0;
k=i;
while(i<=n)
{
if(k==0)
{
if(s==i)
printf("%d\n",i);
i++;
k=i,s=0;
}
else
{
d=k%10;
s=s+d*d*d;
k/=10;
}
}
}
main()
{
int n;
printf("Enter the value of n : ");
scanf("%d",&n);
printf("Armstrong numbers between 1 to %d are :\n",n);
armstrong(n);
getch();
}
```

The mentioned algorithm is O(n*log(n)).

(For each i form 1 to n it performs log(i) calculations).

using Look Up Table?

```
#include <stdio.h>
static int lut[10][10];
void fillup_lut()
{
int i,j;
for(i=1;i<=9;i++)lut[0][i]=1;
lut[0][0]=0;
for(i=1;i<=9;i++)
for(j=0;j<=9;j++)
{
lut[i][j]=lut[i-1][j]*j;
}
}
int armstrong(int i)
{
int a=i;
int no_of_digits=1;
while(a/=10)no_of_digits++;
a=i;int sum=0;
while(a)
{
sum+=lut[no_of_digits][a%10];
a=a/10;
}
if(sum==i)return 1;
else return 0;
}
main()
{
int i;
fillup_lut();
for(i=0;i<99999999;i++)
{
if(armstrong(i)) printf("%d\n",i);
}
}
```

```
#include<iostream>
using namespace std;
main()
{
int x,i,n,sum,p;
cout<<"Enter upper range\n";
cin>>n;
cout<<"0\n";
for(i=1;i<=n;i++){
sum =0;
x=i;
while(x){
p=x%10;
x /= 10;
sum += p*p*p;
}
if(sum ==i ) cout<< i<<endl;
}
}
```

```
public class ArmStrongNumber {
public static void armStrongNumber(int n) {
if (n < 0) {
return;
}
while (n > 0) {
int sum = 0;
int number = n;
while (number > 0) {
int remainder = number % 10;
sum = sum + remainder * remainder * remainder;
number /= 10;
}
if (sum == n) {
System.out.println(n);
}
n--;
}
}
public static void main(String[] args) {
armStrongNumber(999);
}
}
```

```
#include<iostream>
#include<conio.h>
bool isArmstrong(const int number)
{
int a,b,c;
a = number%10;
b = (number/10)%10;
c = (number/100)%10;
return ( ( (a * a * a) + (b * b * b) + ( c * c * c)) == number );
}
int main()
{
std::cout<<"\n Armstrong number are : ";
for ( int i =100;i<1000;i++)
{
if ( isArmstrong(i) )
{
std::cout<<"\t"<<i;
}
}
getch();
}
```

You are considering that range will be between 100 to 1000. But according to the question range can be 10000 also. And also what about the armstrong nos. between 1 to 100. You have not considered that also

There we are not considering one important point..say for example we can prune our search in following scenarios..

- ovjforu September 16, 2012if we know that sum of cubes of say ( 001 ) is = 1 and number itself is 1 then there exists no possibility that there will be any armstrong number between 2-9.. so there by we can resume our search from 10 likewise.. for 1-100.. numbers which we will check are

1, 10-13,20-23,30-32,40 only... we indirectly cut short lot of checks ... this approach will help us discard large range of numbers... also we can use an array of size 10 or 9 .. with precomputed cube...in that way we will reduce even common / repetitive cubic operation...

One additional point of performance improvement is.. when we are changing digits say decimal or tenth then we don't want to compute the whole sum again.. we can store it may be simple on stack.. for current digits sequence of >=10, >=100, >=1000, >=10000,>=100000....etc...

please let me know if this makes any sense...