## Infosys Microsoft Interview Question for Software Engineer / Developers

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

Here is one way to look at the problem. If a number has an even number of *distinct* factors, then the door with that number will be flipped an even number of times. Now, even prime numbers have an even number of factors. But, the doors whose numbers are perfect squares have an odd number of factors. So those doors will be flipped an odd number of times. Since the initial state of all doors was "Closed", those doors that are perfect squares will be flipped to "Open". There are 10 numbers less than or equal to 100 that are perfect squares. So the answer must be 10 doors?? I hope I am right!!

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

Yes, you are correct.

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

The number of toggles of a door determines its final status. If a door is toggled for odd times, it will end up with open. If even time, the door will be closed at the end.

Also noticed that, after nth pass, door number <= n will not be touched anymore.

For door #1, it will be toggled once therefore it will end up open.
For door #2, it will be toggled twice (in pass 1 and 2) and is end up closed.
For door #3, it is toggled twice (pass 1, 3) and ends up closed.
For door #4, it is toggled 3 times (pass 1, 2, 4) and ends up open.
....
For door #100, it is toggled 9 times (pass 1, 2, 4, 5, 10, 20, 25, 50 and 100) and ends up open.

Therefore, this problem can be reduced to finding the numbers that have odd number of factors between 1 and itself, and 1, 4, 9, 16, 25, 36, 49, 64, 81 and 100 has this property. This is because all other numbers have even number of factors that can multiply to itself while the above 10 have one mroe, which is the square root of itself.

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

awesome solution..thanks

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

"

``" you can figure out that for any given door, say door #42, you will visit it for every divisor it has. so 42 has 1 & 42, 2 & 21, 3 & 14, 6 & 7. so on pass 1 i will open the door, pass 2 i will close it, pass 3 open, pass 6 close, pass 7 open, pass 14 close, pass 21 open, pass 42 close. for every pair of divisors the door will just end up back in its initial state. so you might think that every door will end up closed? well what about door #9. 9 has the divisors 1 & 9, 3 & 3. but 3 is repeated because 9 is a perfect square, so you will only visit door #9, on pass 1, 3, and 9... leaving it open at the end. only perfect square doors will be open at the end.  "``

"

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

10

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

Yes answer is sqrt (no_of_doors) always.

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

becoz this is a factorization problem. only perfect squares has odd number of factors.

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

100

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

100 is a wrong answer. look up "programming interviews exposed" or for that matter, simply google!

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

This question was straight out from the "PIE" book. I didn't answer this question correctly but still got an offer.

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

Yes u are correct Sriram...This is exactly what I did.

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

You really shouldn't make big assumptions without formal proof.

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

First pass he opens all the doors

Status after first pass:

Open Doors = 100
Closed Doors =0

Status after second pass:

closes every second i.e even numbered door

Open Doors = 50
Closed Doors = 50

Status after third pass:

He meets 100/3 = 33 doors on his way.

3,6,9,12,15.......99

even numbered doors : 100/6 = 12

out of 33 doors 12 are even i.e which were closed are now open.

out of 33 doors 21 are odd i.e which were open before are now closed.

over all change : 21-12 = 9 closed doors added to the status.

Open Doors = 41
Closed Doors = 59

41 doors are open after his third pass.

Remarks:
Guys this is what I think the correct answer please let me know if I am correct and add your method of solving this. Thank you very much.

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

Oops I got the question wrong... I read it as only 3 passes... lemme try it again..

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

I din't know how to slove it jus using pen and paper so I wrote a program and the result is

01
Door open 1
001
Door open 4
00001
Door open 9
0000001
Door open 16
000000001
Door open 25
00000000001
Door open 36
0000000000001
Door open 49
000000000000001
Door open 64
00000000000000001
Door open 81
000000000000000000
Doors open = 9
Doors closed = 91
Press any key to continue

I will to solve it and explain it in details if I get it... mean while please let me know if you get it..

Thank you

Pavankumar Bondugula

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

Hey Sam,

That is so clear... thank you. Now, I got it.

Pavankumar Bondugula

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

thanks Sam

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

well the answer is surely 10.
its the no of perfect squares u have below 100.
the logic by sri is exactly the core of the problem.
its all about the no of factors a perfect square has...

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

This Code works and gives the correct output .. which is different from that given above...

#include <stdio.h>
main()
{
static int rooms[100];
int i,j;

for(i=1;i<=100;i++)
{
if(i%2==0)
{
for(j=1;j<=100;j++)
{
if(j%i==0)
{
rooms[j-1]=0;
printf("Closed Room : %d\n",j);
}
}
}
else
{
for(j=1;j<=100;j++)
{
if((j%i)==0)
{
if(rooms[j-1]==0)
{
rooms[j-1]=1;
printf("Opened Room No : %d\n",j);
}

else
{
rooms[j-1]=0;
printf("Closed Room No : %d\n",j);
}
}
else
continue;
}
}
printf("---------------------------PASS %d Ended-----------------------------------\n\n\n",i);
}

for(i=0;i<100;i++)
{
if(rooms[i]==1)
printf("Room No : %d \n",i+1);

}
}

Output:
Rooms opened: 1,9,25,49,81

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

This Code works and gives the correct output .. which is different from that given above...

#include <stdio.h>
main()
{
static int rooms[100];
int i,j;

for(i=1;i<=100;i++)
{
if(i%2==0)
{
for(j=1;j<=100;j++)
{
if(j%i==0)
{
rooms[j-1]=0;
printf("Closed Room : %d\n",j);
}
}
}
else
{
for(j=1;j<=100;j++)
{
if((j%i)==0)
{
if(rooms[j-1]==0)
{
rooms[j-1]=1;
printf("Opened Room No : %d\n",j);
}

else
{
rooms[j-1]=0;
printf("Closed Room No : %d\n",j);
}
}
else
continue;
}
}
printf("---------------------------PASS %d Ended-----------------------------------\n\n\n",i);
}

for(i=0;i<100;i++)
{
if(rooms[i]==1)
printf("Room No : %d \n",i+1);

}
}

Output:
Rooms opened: 1,9,25,49,81

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

All squares will be open since squares are the only ones having odd number of factors.
Example:- 1 has only 1 factor. 4 has factors, 1,2 and 4., 9 has 1,3 and 9.
16 has 1,2,4,8,16. As observed, squares have odd number of factors and hence odd number of visits. They will be open.

10 has 1,2,5,10 - even factors.
12 has 1,2,3,4,6,12 - even factors.
Prime number 3 has 1 and 3. 5 has 1 and 5. All 2 factors.

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

Cant be clearer than SAM. Nice one man. I was actually breaking my heads out with all factors and stuff.. sheeesh!

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

An excellent Solution man!!!!!!!!!!!!

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

10 ( Number of Perfect Squares less than equal to 100)

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

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

No, i'm sorry. I think the answer is 51.

Name:

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

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

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