can someone help me on this tricky interview math question?

Question

so there are 10,000 lamps in one line with an on/off switch on each lamp and 10,000 people are in row standing next to the lamps. The lamps are off. So the first person goes (one by one, people go), and stops by every lamp (changes the current state:turns on every lamp). The second person stops by every second lamp starting from the second and changes the state of each of those lamps. The third goes and stops by every third.. and there is the idea. The question is how would each lamp look (on or off, and there are 10,000 lamps with 10,000 people who walked by) by the time all 10,000 people stopped by and did their duty? This isnt supposed to be easy, it was an interview question for a programming job. Please dont flood answers with "i dont know"

Answer 1

if you want the algorithm will be like this

// initial state set all lamps OFF
1. Lamp[10000]
2. for i = 1 to 10000
{ Lamp [i] = FALSE } // False = OFF

3. for i = 1 to 10000 step 1
4. for J = i to 10000 step i
5. { Lamp[J] = NOT Lamp[J] }


Or if you have sql2000
do two step below
====================
declare @i int
declare @j int
set @i =1
while @i <=10000
begin
insert into lamp(lamp) values(0)
set @i = @i +1
end
==========================
declare @i int
declare @j int
set @i =1
while @i <=10000
begin
set @j =@i
while @j <=10000
begin
update Lamp set lamp=~lamp where id=@j
set @j = @j +@i
end
set @i = @i +1
end
====================================

Check the result
select lamp,count(*)
from lamp group by lamp
Status::Qty
0::9900 = 9900 lamps OFF
1::100 = 100 lamps ON

Answer 2

I'm not sure how to write a program for this, but it is actually a very simple problem.

The lamps are going to be switched on or off exactly as many times as they have factors (if we number the lamps 1, 2, 3,...).

All numbers have an even number of factors EXCEPT square numbers, which have an odd number of factors.

If all of the lamps start off, then the ones with even factors (non-square numbers) will be off at the end and the square numbered lamps (1, 4, 9, 16, ....) will be turned on.

Answer 3

How odd. 99 Lamps will be on in the end. I solved it using a perl script...

#!/usr/bin/perl
for ($i=0; $i<10000; ++$i) {
for ($j=0; $j<10000; $j += ($i+1) ) {
$s[$j] = $s[$j] ^ 1;
}
}

for ($i=0 ; $i < 10000 ; $i++) {
$n++ if ($s[$i]);
}

print "$n lamps are on\n";

In general, the answer is one less than the square root of the number of lamps (and people) if the number is a perfect square, otherwise it's equal to the integer portion of the square root of the number of lamps. I tried it for quite a few other values and this relationship holds up. I suspect it's related to this: http://en.wikipedia.org/wiki/Integer_square_root

Answer 4

every odd numbered lamp will be on and even numbered lights would be off the fist lamp is turned on and not touched again the second lamp is turned off by the second person and then not touched again an d so on

Answer 5

All of the odd numbered lamps such as the 1,3, and 9999 would be opposite of their original position. So in this case they would all be on.

All of the even numbered lamps such as 2,4, and 10000 would be the same as their original position. So in this case they would all be off.

This is because the amount each lamp switch is fliped is based on the number of the lamp. For lamp 1, it is just flipped once. So it will be opposite of the original position.This is the case for all odd numbered lamps. For lamp 2, it is flipped on then off since it is flipped twice. This is the case for all even numbered lamps.

Answer 6

That's kind of an extreme job interview question! I would be so shocked to get a question like that....

My guess would be that they are all off because 10,000 is an even number, and if somone flips the switch or whatever an even number of times, it will go back to its original position. But I could be wrong! How did your job interview go? Did you get the job? Or don't you know yet? Let me know if you want to...

~Alicia

Answer 7

ok try this the first ten lamps will be on off off on off off off off on off it will go up by two for the offs and always have only one on in between so i figure that seven thousand will be off and three thousan will be on dont know if its right but i think it might be reasonable

Answer 8

What have you tried when it comes to programming this? Post what you have so far, I'd be happy to build on it.

Answer 9

they would be off becasue the light bulbs would burn out