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 –

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.