## Count Open Lockers [Problem of the Week]

Last week’s problem was a mistake – I had to suffer LOTS of code tracing and compiling. I had a troublesome “code” week here and in work ..

Anyway, as a result, no coding this week – just pure brain-work!

This week’s problem is a brainteaser, also is asked in interviews. The main point behind it is to show your interviewer how you could think to solve difficult, vague problems. Here’s the problem ..

Suppose you are in a hallway lined with 100 closed lockers. You begin by opening all 100 lockers. Next, you close every second locker. Then you go to every third locker and close it if it is open or open it if it is closed (call this

togglingthe locker). You continue toggling everynth locker on pass numbern. After your hundredth pass of the hallway, in which you toggle only locker number 100, how many lockers are open?In a hall with

klockers, how many lockers remain open after passk?

I’m sure I’ll get tons of questions about that, so here’s a *second* explanation: Imagine this hallway of 100 lockers. You make “passes” on these lockers ..

**1st pass:**All lockers are closed. So you ‘open’ them all (1, 2, 3, 4, 5, …).**2nd pass:**All lockers are open. You ‘close’ only every second locker (2, 4, 6, 8, 10, …).**3rd pass:**You don’t know which locker is open and which is closed during the pass, so we’ll just ‘toggle’ every third locker (3, 6, 9, 12, 15, …).**nth pass:**Continue similarly ..

No code, just the how ..

And before you even try, the solution won’t be **literally** counting the lockers or handwriting the passes till the 100th! LOL

for every locker i count the number of numbers that it is divisible by …. if it was odd then it’s open if it’s even then it’s closed

TeCNoYoTTaSeptember 1, 2008 at 5:53 pm

This is a nice problem that I was asked before but not in an interview π

each locker will be toggled let’s say for m times where m is the number of factors for the number of the locker including both 1 and the locker number itself

so for example ,for locker number 34 it’s initially closed like any other locker as you stated and it will be toggled as the following:

pass no 1:it’s open

pass no 2: closed

pass no 17: open

pass no 34: closed

All the locker numbers with even number of factors will be closed after the last pass

so the locker numbers with ODD number of factors will be the only lockers which will be left open and that will be for the lockers with perfect square number (1,4,9,16,25,36,49,64,81,100)

Mohamed AbdelghaniSeptember 1, 2008 at 6:01 pm

TWO WINNERS.. seems it’s easy this time, huh? π1. Mohamed Abdelghani (couldn’t be better!! (Y) )

2. TeCNoYoTTa (eventhough you didn’t actually give a specific answer to the first question, but I’ll count it)

Anyone else … ???

AlaaShakerSeptember 2, 2008 at 12:00 am

the number of open lockers will be the number of perfect squares from 1 to k

the 1 will be included as perfect square

JaqoupSeptember 2, 2008 at 2:33 pm

A THIRD WINNER.. Jaqoup πAlaaShakerSeptember 2, 2008 at 2:36 pm

This is similar to problem in UVa (Light, more light) :d

what about this relation :

if (k) is perfect square , then the number of open lockers in a hall with (k) lockers = square root of (k).

else

the number of open lockers in a hall with (k) lockers = the root of the previous perfect square of the number (k).

Mohamed Abd El-Mon'em (Harry Potter)September 2, 2008 at 5:09 pm

FOURTH.. Mohamed Abd El-Mon’em (Harry Potter) ..Long Live ACMers loooool

AlaaShakerSeptember 2, 2008 at 5:23 pm

Will try to explain the idea as much as I can, but after giving the final direct answer to your question..

>

In a hall with k lockers, how many lockers remain open after pass k?N lockers, where the square of N is the biggest you can get

withinthe range of K ( less than or equal k).So for a hall with100 closed lockers, the answer would be 10,

square(10) <= 100 … TRUE

square(11) <=100 … FALSE

========

How is that?

Each locker within range K will be accessed EVEN number of times/passes( meaning, its status remains unchanged.. !(!TRUE) == TRUE) except the squares(numbers with ODD number of factors), as they are a result of a number multiplied by itself..(not two unique numbers).

EX:

Locker #4

3 factors: 1, 2 , 4.

Will be accessed on the first, second and fourth pass ( ODD ).

Meaning it’s final status will be the inverse of the initial one ( OPEN).

Metal_September 2, 2008 at 6:06 pm

FIFTH WINNER.. Metal .. straight As πAlaaShakerSeptember 2, 2008 at 6:08 pm

look alaa π I got how to get the number of remaining lockers

If lockers are K , then opened lockers r the integer value of rootsquare of K

if k = 10 and the rootsquare of 10 is 3.16

then number remaining open lockers r 3 lockers π

if k = 85 and the rootsquare of 85 is 9.21

then the remainin are 9 lockers

btw rootsquare 100 is 10 π , hehehe

donno wat is that LOOL but it is how i got it π

try it on any number π wokring

Mohamed Hesham - FilipinoSeptember 2, 2008 at 8:37 pm

SIXTH.. Mohamed Hesham – Filipino ..It’s right, even though you have no idea how you reached that! loooool

AlaaShakerSeptember 3, 2008 at 2:49 am

[…] Open Lockers SOLVED [Problem of the Week] Seems this week’s problem was quite easy – five winners in less than two […]

Count Open Lockers SOLVED [Problem of the Week] « AlaaShaker’s WeblogSeptember 3, 2008 at 4:12 am

oh no i knew the answer i just went to pray and when i returned i found it solved

please make it for longer time 4 the next one ,thanks π¦

AhdSeptember 3, 2008 at 5:00 am

To Ahd:The rules for every ‘Problem of the Week’ is that I post the solution on Friday, or when I get five correct solutions – the earlier!

I got six this time ..

Plus, I make sure solutions are posted separately so anyone who

stillwants to solve the problems, could do so π Anyway, will try to postpone that a little next time ..AlaaShakerSeptember 3, 2008 at 5:02 am

You post a new question weekly?

JustWonderingOctober 22, 2009 at 6:55 am

The statement in the question is not correct to decide if we can apply even and odd, facots or perfact sqaures.

Let try to plot this thing in excel and you will find all the answers are wrong.

The term toggling is specified to be repetative. and is not mentioning that once the door is toggled then you are not allowed to toggle it again hence all the above answer are false.

Samay ManeJuly 29, 2010 at 4:44 pm