Mr. Zargas was the zany math teacher at Cliffmont High that everyone seemed to love. Whether you were a nerd or a jock, he made mathematics interesting, challenging, and fun to learn. That, in and of itself, was impressive enough, but Mr. Zargus took it one step further. When it came time for his frequent "Mathematical Battle of Wits," he would let the jocks use their brawn instead of their brains. The nerds never stood a chance, especially when it came to his "locker challenge."

The rules of Mr. Zargas' locker challenge were simple. Corridor G was a long-since abandoned section of Cliffmont High that a row of 100 unused, empty lockers. If you "toggled" the state of each locker (i.e. opening it if its closed, closing it if its open) in the following manner, which lockers would remain open?

  1. Every single locker is toggled (since all lockers start closed, this means each one is opened).
  2. Every other locker is toggled (in this case, closed), starting with the second.
  3. Every third locker is toggled, starting with the third.
  4. Every fourth locker is toggled, starting with the forth.
  5. ...
  6. The hundredth locker is toggled.

The jocks had it easy; they could simply run up and down the hallway, opening and closing the lockers until they answered the question. But the nerds had a real challenge: they had to answer the question without counting or using any other "brute force" method. They could only use deductive logic and formulas to solve the problem.

Year after year — no matter how hard the nerds tried — the jocks would always win. They simply ran, opened, and closed faster than the nerds could think. And seeing that the locker challenge always played out during football season, losing was a particularly embarrassing defeat since the jocks got to pummel the nerds on the field later that day in gym class.

Can You Beat the Jocks?

The rules to your challenge are just as simple. Develop a function that determines which lockers would remain open after toggling n lockers in the manner described above. There should be one input to the function (number of lockers) and one output (representation of which lockers remain open; string, array, etc).

getOpenLockers( 1 ) --> { 1 }
getOpenLockers( 4 ) --> { 1, 4 }

And remember, like the nerds, no brute force methods allowed. And if you really want to impress, identify which lockers would be toggled the most.

To Get Started...

Following is a simulation built using the jocks' brute-force method. It also serves as a timer to see if you can beat the jocks.

Locker count:
Milliseconds per toggle:
 
 

Now don't watch the simulation for too long, lest one of the jocks might catch you sneaking a peak and stuff you in a locker.

Got a tip for a future Programming Praxis? Please send it on in!

[Advertisement] BuildMaster allows you to create a self-service release management platform that allows different teams to manage their applications. Explore how!