AlaaShaker's Weblog

// untitled …

Count Open Lockers [Problem of the Week]

with 16 comments

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 ..

Lockers

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

SOLVED here

Advertisements

Written by AlaaShaker

September 1, 2008 at 2:37 pm

16 Responses

Subscribe to comments with RSS.

  1. 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

  2. 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

  3. 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

  4. 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

  5. A THIRD WINNER .. Jaqoup πŸ˜€

    AlaaShaker

    September 2, 2008 at 2:36 pm

  6. 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

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

    AlaaShaker

    September 2, 2008 at 5:23 pm

  8. 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

  9. FIFTH WINNER .. Metal .. straight As πŸ˜‰

    AlaaShaker

    September 2, 2008 at 6:08 pm

  10. 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 - Filipino

    September 2, 2008 at 8:37 pm

  11. 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

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

  13. 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

  14. 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

  15. You post a new question weekly?

    JustWondering

    October 22, 2009 at 6:55 am

  16. 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 Mane

    July 29, 2010 at 4:44 pm


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: