#### Good job! You’re all caught up

Earlier Dismiss All

## July 20, 2017 Playing with Problems II

Continuing on last week’s theme of “playing with problems” let’s try it out with another fun problem: opening doors!

There are n closed doors in a long corridor, numbered 1 to n. A person walks through and opens each door. Another person walks through and closes every alternate door. This continues with the i-th person toggling the state of every i-th door. How many doors are left open after the nth person is done?

Well the problem is simple enough to understand, so we can whip out our editors and dash off a solution in no time!
This, as you know from my previous blog is a mistake…

## Rushing to a Solution

If, as we saw in the blog, we rush to the solution we may implement a solution like this:

int doors_open(int n) {
int doors[n];
for(int i = 1;i <= n;i++) {
int p = i;
while (p <= n) {
doors[p-1] = !doors[p-1];  /* toggle */
p += i;
}
}
return std::count(doors, doors+n, 1);
}


Then we’ll spend time trying to optimize it (let’s use a bitset!) and use all the technical wizardry and deep knowledge we are so good at. However, our solution will most likely remain O(n log(n)).

## Playing with the Problem

Instead, if we play around with the problem for a bit we will begin to notice a pattern –

For 1 door – Doors open: 1
For 2 doors – Doors open: 1
For 3 doors – Doors open: 1
For 4 doors – Doors open: 1, 4
For 5 doors – Doors open: 1, 4
For 6 door – Doors open: 1, 4
For 7 doors – Doors open: 1, 4
For 8 doors – Doors open: 1, 4
For 9 doors – Doors open: 1, 4, 9
For 10 doors – Doors open: 1, 4, 9

Now we can clearly see a pattern. Why does this happen? Well, play with the problem for a bit and you will figure it out!
Once we understand it the pattern, the solution becomes so much simpler!

int doors_open(int n) {
return std::sqrt(n); /* neat huh? */
}


## The Explanation

If you’ve played with the problem and still can’t figure it out – I’ll explain it for you. But before you read ahead, do promise you’ve tried it out yourself.
Ok so if we think about it, door 1 will be touched only by person 1, door 2 will be touched by person 1 and 2, door 3 will be touched by person 1 and 3, and so on. In general door i will be touched by all the divisors of i upto i.

    Door 6               Door 9
|                   |
1  2  3  6            1  3  9


Now every divisor has a corresponding “pair”

which means that whatever x does, y will simply undo. Therefore the door state will not change.
The only time we don’t have a “pair” is when x = y i.e. the number is a square of another number. Therefore only the perfect squares (1,4,9,16,…) are left open. So all we need to know is how many perfect squares are there < n which is sqrt(n).

## Conclusion

As with my last post, I am hoping to show you how important (and fun) it can be to play with the problems given to you before trying to find a solution. This is a hard but excellent habit to cultivate and will stand you in good stead through your career.

charles.lobo

Guest Blogger

categories & Tags

UNLEASH THE GIG ECONOMY. START A PROJECT OR TALK TO SALES
Close