You are standing in a school hallway lined with 100 closed lockers. You then open all 100 lockers. After this, you then close every 2nd locker (so the 2nd, 4th, 6th…98th and 100th are all closed). Then, you go to every third locker and open it if it is closed or close it if it is open (let’s call this toggling the locker for our discussion). You proceed to toggle every nth locker on pass number n. So, for example, on pass number 16 – you will toggle every 16th locker. After your hundredth pass of the hallway, in which you toggle only locker number 100, how many lockers are now open?
In a hall with x lockers, how many lockers remain open after pass number x?
This brain teaser can seem intimidating at first. Just drawing a diagram of 100 lockers and actually toggling each one would not really display any intelligence on your part. In fact, you’d probably look pretty dumb. Clearly, there must be a more intelligent way of solving this problem since you wouldn’t be asked this question if there weren’t some smarter, more efficient way of solving this.
Start out small with this problem
This isn’t the type of problem that gets solved just by staring at it and hoping an answer just comes to you. So, a good idea is to try some different numbers (much smaller than 100, of course), and see if that helps you notice some patterns.
Let’s just start by choosing a random locker, and let’s determine whether it will end up open or closed. Let’s choose locker # 6.
Let’s go through each pass:
Pass # 1: all lockers are opened, including locker # 6
Passes greater than 6: Locker #6 will not be toggled again, since those will all start farther down the hall.
So, one thing you may notice after running through this example is that locker #6 is only toggled when the number of the pass (also called “x”) that you are on is a factor of the # 6 – you can see that 1,2, 3, and 6 are all factors of 6. And those are all the passes on which the locker 6 is toggled – the sequence is open, close, open and then close. So, locker # 6 ends up closed.
Now that sounds like promising information. Since we are dealing with factors here, why not try a prime number – since a prime number only has 2 factors – itself and ‘1’. Let’s try the number 13 as our prime number. The factors are 1 and 13 – which means that the operations are open and then close for any pass greater or equal to 13. So, it ends up being closed.
So, we know one thing for sure: that the lockers are only toggled on passes that are factors of the individual locker number.
Do the math – It’s all about the factors
What else do we know? Well, we know that lockers are closed every 2nd, 4th, 6th, etc. times they are toggled – so if a locker is toggled an even number of times it ends up closed, otherwise it ends up open. Combining this knowledge with our other knowledge, we can say that a locker will end up closed if it has an even number of factors, because the number of times a locker is toggled equals the number of factors. If a locker has an odd # of factors, the locker will end up being open.
So, this knowledge makes a big difference – we’ve really simplied the problem – now all we need to do is figure out how many numbers between 1 and 100 have an odd # of factors, and we will have our answer!
First, let’s jump into the math to find our answer.
Well, it means that c multiplied by some other number b is equal to d. This also means that b is also a factor of d since multiplication is commutative (c*b = b*c).
But, what if the factors are the same numbers – if b is equal to c? Then, the number d would be a perfect square, since b*b would equal d, which would be a perfect square. This would also mean that we would have an odd number of factors – and an odd number of factors would mean that particular locker will remain open.
Since there aren’t very many perfect squares between 1 and 100, you can list them out – here they are: 1, 4, 9, 16, 25, 36, 49, 64, 81 and 100 – so, exactly 10 lockers will remain open.
Generalizing the solution to this brain teaser
Now, let’s generalize the solution so that we have an answer to the original question:
If there are x lockers, the number of open lockers will be the number of perfect squares between 1 and x (inclusive). To count them, all you need to do is find the square root of the largest perfect square less than or equal to x. So, the general solution would be: floor(sqrt(x))
Here’s an example to help illustrate this:
And because floor(sqrt(200)) = 14,
… there will be 14 open lockers.
In an interview situation you may not have been able to easily get to the answer here. But, the most important thing is that you give it your best shot, and you approach it intelligently!
Here, you should also see the value of breaking the problem down into a more manageable size, finding a pattern, and then coming up with a solution.