I encountered this in a job interview today, and I'm totally stumped. Here's a description of the problem:
You have a set of lights from 1 to 100 inside a room, and 100 people. The i-th person walks into the room and turns on all the lights numbered that are a multiple of i. If that light is already turned on, they will turn it off (i.e. they will toggle the light). 100 is just random number -- the solution should work up to some arbitrary value N (N == number of lights == number of people).
For instance, person 1 will turn on all the lights (as every number is a multiple of 1). Person 2 will toggle all the lights that are a multiple of 2 (2,4,6,8, and so on). This continues up to the 100th person.
At the time, I got the feeling that this might have something to do with trying to determine prime numbers up to N, but I wasn't 100% sure, so I went with a kind of brute force approach (here's roughly what I provided in PHP):
function lights_toggled($number_of_lights) {
$toggly = function($idx, $lights) {
foreach($lights as $i => $light) {
if($i % $idx == 0) {
if($lights[$i]) {
$lights[$i] = 0;
} else if(!$lights[$i]) {
$lights[$i] = 1;
}
}
}
return $lights;
};
$lights = array_fill(1,$number_of_lights,0);
for($i = 1; $i <= count($lights); $i++) {
$lights = $toggly($i, $lights);
}
return array_sum($lights);
}
I thought all was well and good, until I got home and started looking at inputs + outputs of this function. I did something like this to get some sample results:
$results = array();
for($j = 1; $j <= 100; $j++) {
$number_of_lights_on = lights_toggled($j);
$results[$number_of_lights_on][] = $j;
}
print_r($results);
It's long, so here's a snippet of the output for when # of lights ON == 3 or 4:
...
[3] => Array
(
[0] => 9
[1] => 10
[2] => 11
[3] => 12
[4] => 13
[5] => 14
[6] => 15
)
[4] => Array
(
[0] => 16
[1] => 17
[2] => 18
[3] => 19
[4] => 20
[5] => 21
[6] => 22
[7] => 23
[8] => 24
)
...
When the number of lights is between 9 and 15, the answer is 3 lights on. When the number of lights is between 16 and 24, the answer is 4 lights on. Basically, it seems when when x lights returns as the answer, the lower bound of number of total lights is x^2 and it's upper bound is x(x+2).
I am starting to see structure here, but I can't put my finger on whether this result follows an algorithm that I just don't remember or know about.