## 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]; std::fill(doors, doors+n, 0); /* start with closed doors */ 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 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 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