100 Doors Problem

There are 100 doors in a row that are all initially closed.

You make 100 passes by the doors.

The first time through, visit every door and  toggle  the door. (open if closed, close if opened).

The second time, only visit every 2nd door   (door #2, #4, #6, ...),   and toggle it.

The third time, visit every 3rd door   (door #3, #6, #9, ...), etc,   until you only visit the 100th door.

What needs to be done?

Every time you pass ask a question which doors are open and which ones are closed? If they are opened close them if they are closed open them.

Complex Solution:

<?php

// There are 100 doors in a row that are all initially closed.
$doors = array_fill(1, 100, false);

// You make 100 passes by the doors.
for ($pass = 1; $pass <= 100; ++$pass) {

    // The first time through, visit every door and  toggle  the door
    // (if the door is closed,  open it;   if it is open,  close it).
    for ($nr = 1; $nr <= 100; ++$nr) {

        // The second time, only visit every 2nd door   (door #2, #4, #6, ...)
        // The third time, visit every 3rd door   (door #3, #6, #9, ...), etc
        if ($nr % $pass == 0) {
            $doors[$nr] = !$doors[$nr];
        }
    }
}

echo "Doors: ";
for ($nr = 1; $nr <= 100; ++$nr) {
    echo ($doors[$nr]) ? 'O': 'C';
}

Above solution looks great however it is complex. You can easily see that it has O(n2) complexity.

To solve above problem with less complexity we will have a look at following simple solution:

If we notice above solution then you will notice that the doors that are open at the end are perfect squares of integers. i.e 1, 4, 9, 16, 25 etc.

So, changing above solution to following would work:

<?php

echo "\nDoors: ";
for ($i = 1; $i <= 100; $i++) {
    $root = sqrt($i);
    echo ($root == ceil($root)) ? 'O' : 'C';
}
echo PHP_EOL;

I hope you find this article useful. If you have any solutions regarding this article send me via contact form with your name and I will post them here.