Graham Walters

A wee site for the things I do

The Lockers Problem

I was recently asked to solve the following problem:

There are 1000 lockers in a high school with 1000 students. The problem begins with the first student opening all 1000 lockers; next the second student closes lockers 2,4,6,8,10 and so on to locker 1000; the third student changes the state (opens lockers closed, closes lockers open) on lockers 3,6,9,12,15 and so on; the fourth student changes the state of lockers 4,8,12,16 and so on. This goes on until every student has had a turn.

How many lockers will be open at the end?

Without researching the problem I decided to write the following JavaScript program.

After I finished the program I looked into the problem to verify the answer my solution produced. I discovered that all open lockers are perfect squares (when the square root of a number is a whole number). Equipped with this knowledge I wrote the following JavaScript program making use of the Number.isInteger and Math.sqrt functions.

Having written two versions which both produce the correct answer, I thought it would be worth comparing their performance. A test file was created which would run each version 100 times and average the times. Version 1 took an average of 96255.61 nanoseconds whereas version 2 took 65891.69 nanoseconds.

If you’re interested in learning more about this problem, I recommend reading the following links link 1 and link 2.

This entry was tagged Math JavaScript