Note: This is more of a math problem than an algorithm, yet it's a nice, fun one to play with, so I'm going for it.
You have 100 doors in a row that are all initially closed. You make 100 passes by the doors.
The first time through, you visit every door and toggle the door (if the door is closed, you open it; if it is open, you close it). The second time you only visit every 2nd door (#2, #4, #6, ...). The third time, every 3rd door (#3, #6, #9, ...), etc, until you only visit the 100th door.
Question: What state are the doors in after the last pass? Which are open, which are closed?
Let's pick a random door number to see it's final state, just to have a better understanding. The 8th door it is!
- At the end of your first pass, all 100 will be opened. (#8 open)
- 2nd time you skip the odd numbers, meaning only 2nd, 4th, 6th....100th will be closed, thus all odd ones remain open. (#8 closed)
- 3rd pass => 3n (3, 6, 9, 12, 15, 18...) (#8 still closed)
- 4th pass => 4n (4, 8, 12, 16...) (#8 opened)
- 5th pass => 5n (5, 10, 15...) (#8 still open)
- 6th pass => 6n (6, 12, 18...) (#8 still open)
- 7th pass => 7n (7, 14, 21...) (#8 still open)
- 8th pass => 8n (8, 16, 24...) (#8 is now closed) - Now, from here onwards no pass would stop by the #8th door.
- 9th pass => 9n (9, 18, 27...)
- 10th pass => 10n (10, 20, 30...)
- 11th pass => 11n (11, 22, 33...)
So you only change the 8th doors state on the 1st, 2nd, 4th and 8th pass. 1 - 2 - 4 - 8 ... these are factors of 8 (actually just 2 and 4).
Let's check above steps for a prime number, 11 : The factors are only 1 and 11, it's easy to see that only times you interact with #11 are 1st and 11th passes.
So, we can easily say that the only times you interact with a specific door are the passes that represent factors of the door number.
How about the final states of these doors?
Well,
- #8 ended up closed, 11th as well (1st pass opens, 11th closes).
- The very 1st door is interacted only once and remains open.
- See the #9 above; 1st pass opens, 3rd closes, from 9th onwards it remains open.
- Check #4, 1st pass opens, 2nd closes, 4th opens it back and that's it.
Can you spot the pattern here now?
- Door 1 => 1 interaction, 1 factor, final state = OPEN
- Door 4 => 3 interactions, 3 factors, final state = OPEN
- Door 8 => 4 interactions, 4 factors, final state = CLOSED
- Door 9 => 3 interactions, 3 factors, final state = OPEN
- Door 11 => 2 interactions, 2 factors, final state = CLOSED
Those which have ODD number of factors end up being OPEN and those which have EVEN number of factors end up as CLOSED.
On the other hand it's easy to see that #1, #4, #9 are perfect squares, they also happen to be the ones that remain OPEN.
Based on these findings one could say that all perfect squares will remain OPEN. Wanna test a few more of them? There we go.
- #16
- factors: 1, 2, 4, 8, 16
- interactions: same number as it's factors, 5 (ODD)
- final state = OPEN
- #25
- factors: 1, 5, 25
- interactions: same number as it's factors, 3 (ODD)
- final state = OPEN
Now the question is... How many perfect squares are there between 1 and 100?
That's quite easy to find out by getting the integer value of the square root of 100.
floor(sqrt(100)); // 10
Want to check it out? [ 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 ] ... There they are.
You can try this for any given range. Let's test 200.
floor(sqrt(200)); // 14
Which are = [ 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196 ].
So the total number of doors that will remain open are 10! The rest 90 doors will remain closed.
Now, after a loooong and detailed explanation, let's try a full code that'd print us all door states.
for ($x = 1; $x <= 100; $x++) {
$root = sqrt($x);
$state = ($root == floor($root)) ? 'open' : 'closed';
echo "Door $x: $state\n";
}Here is the 3v4l where you can see the output :)