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 toggling the locker). You continue toggling every nth locker on pass number n. After your hundredth pass of the hallway, in which you toggle only locker number 100, how many lockers are open?
In a hall with k lockers, how many lockers remain open after pass k?
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
RSS - Posts
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
TeCNoYoTTa
September 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 Abdelghani
September 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 … ???
AlaaShaker
September 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
Jaqoup
September 2, 2008 at 2:33 pm
A THIRD WINNER .. Jaqoup
AlaaShaker
September 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
AlaaShaker
September 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 within the 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
AlaaShaker
September 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
, hehehe
wokring
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
donno wat is that LOOL but it is how i got it
try it on any number
Mohamed Hesham - Filipino
September 2, 2008 at 8:37 pm
SIXTH .. Mohamed Hesham – Filipino ..
It’s right, even though you have no idea how you reached that! loooool
AlaaShaker
September 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 Weblog
September 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
Ahd
September 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 still wants to solve the problems, could do so
Anyway, will try to postpone that a little next time ..
AlaaShaker
September 3, 2008 at 5:02 am
You post a new question weekly?
JustWondering
October 22, 2009 at 6:55 am