## Microsoft Interview Question students

• 0

To generate armstrong numbers ...In O(n)..

Country: United States

Comment hidden because of low score. Click to expand.
1
of 1 vote

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);
}
}``````

Comment hidden because of low score. Click to expand.
0

Please explain the logic of how lookup table is being filled ?

Comment hidden because of low score. Click to expand.
0

What if I say generate first 10 armstrong numbers?(i.e.you dont know value of 'n'.)Time complexity isn't of order of 'n'

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````#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();
}``````

Comment hidden because of low score. Click to expand.
0

The mentioned algorithm is O(n*log(n)).
(For each i form 1 to n it performs log(i) calculations).

Comment hidden because of low score. Click to expand.
1
of 1 vote

There we are not considering one important point..say for example we can prune our search in following scenarios..
if 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...

Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) space ..or time?? and till what range?? could you please be specific with the question??

Comment hidden because of low score. Click to expand.
0
of 0 vote

Complexity in the range of O(nLogn).

int armstrong(int n){
int i=0;
for(int i;i<n;i++){

int num=i;
int num_of_digits=(logi/log10)+1;
int sum=0;
while(num!=0){
int digit=num%10;
num/=10;
sum+=pow(digit,num_of_digits);
}
if(sum==i) cout<<"arm num"<<i<<"\n";
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

above algo is incorrect, as it is checking if given num if armstring or not, but above question is different as its asking to generate armstring numbers for given range.....

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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;
}
}``````

Comment hidden because of low score. Click to expand.
0

Kindly check the definition of Armstrong nos.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think it's quite easy to show that an armstrong number must be less than 10^ 4 (think about how big the sum of digits can possibly be). So technically you can do this in constant time!

Comment hidden because of low score. Click to expand.
0
of 0 vote

rajeevpodar is right...
the series is bounded and all the numbers lie between 100 to 1000.
1 = 1^3... except the most obvious answer 1, all the other numbers will be captured with the range given in code

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}

}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````#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();
}``````

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

rajeevpodar is right...
the series is bounded and all the numbers lie between 100 to 1000.
1 = 1^3... except the most obvious answer 1, all the other numbers will be captured with the range given in code

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.