Infosys Microsoft Interview Question Software Engineer / Developers
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.
"
" 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. "
"
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
Final Answer:
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.
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
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
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
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.
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!!
- Sriram Krishnaswami June 27, 2005