AlaaShaker's Weblog

// untitled …

Count Open Lockers SOLVED [Problem of the Week]

with 4 comments

Seems this week’s problem was quite easy – five winners in less than two days!

Such problem is meant to look overwhelming. It would be very pointless if you thought of solving it by drawing a diagram of 100 lockers and literally ‘performed’ the 100 passes to know the solution. If this was an interview, be sure that you’ll be kicked out before you notice it!

First thing, forget the brute-force solution, since – again – it’s all about how you tackle the problem; that’s what the interviewer wants to see.
Go for a random number and give it a try – perhaps you could notice a sequence or a pattern. Let’s pick, mmm, 8?! Sounds good to me ..

lockers_sample

After the 8th pass, you end up with only 2 lockers left open. We notice that the 8th locker was ‘toggled’ in the passes number 1, 2, 4 and 8 (i.e. all factors of 8 ) with corresponding operations of open, close, open, and close – hence, it ends up closed. Now that we talked about factors, I guess we should try a prime number as primes have some unique properties. Let’s try 17. The only times this locker is toggled is in the 1st and 17th passes only (i.e. open, close) and hence, it ends up closed – no big difference then, primes and non-primes act the same!

But we do notice one more thing, if the nth locker toggles an even number of times, it ends up closed again, otherwise, it ends up open. This depends on the number of factors of that number n, meaning that you can safely assume that a locker will end up open if it has an odd number of factors.

This hugely reduces down the problem – all we need to do now is to know how many numbers between 1 and 100 that have an odd number of factors, and that’s the answer!

A bit of math now. What does it mean when we say that i is a factor of n? It means that (i x j = n), where j is some other number. Since multiplication operation is commutative (i x j = j x i), we can say that j is also a factor of n. Therefore, factors always come in ‘pairs’. But since multiplication is also a binary operation, it involves two number to get such operation done – except, if i equals to j, in this case, the pair is formed of only one single number, that effectively forms both halves of the pair, leading us to an odd number of factors! This specific case happens only when n is a perfect square. Try 16?? It ends open!

Consequently, if k is a perfect square, it ends open, otherwise, ends closed. Then in our case when k = 100, the perfect squares between 1 and 100 are 1, 4, 9, 16, 25, 36, 49, 64, 81 and 100 – exactly 10 lockers will remain open.

Generalizing that observation, in the case of k lockers, the number of open lockers is the number of the perfect square between 1 and k (inclusive). To count them, you just need to find the square root of the largest perfect square less than or equal to k. Hence, the general solution would be: floor(sqrt(k))

Example:

If k = 64, then sqrt(64) = 8.246211 ..
And since floor(sqrt(64)) = 8,
… there will be 8 open lockers.

Again, the only point of such problems is to show how you could devise difference strategies to tackle the problem – they might lead you to a result, or to nowhere, it doesn’t matter! In the worst cases, you show your interviewer that difficult problems do not intimidate you.

Winners:

  • Mohamed Abdelghani
  • TeCNoYoTTa
  • Jacoup
  • Mohamed Abd El-Mon’em (Harry Potter)
  • Metal
  • Mohamed Hesham – Filipino

Thanks, and see you next week isA ..

Advertisements

Written by AlaaShaker

September 3, 2008 at 4:12 am

4 Responses

Subscribe to comments with RSS.

  1. may be I didn get the desired mathematical explanation but , I tried some cases in each I noticed some kind of sequences and then I got that how it is the largest square between 1 and k ,, u asked about thehow , but u didn ask about the explanation , If mathematical explanation is required in interview and I must get em tha answer in INSTANT then am kicked before I even try to think ..

    Mohamed Hesham

    September 3, 2008 at 1:49 pm

  2. No. Interviewers won’t give you a text box and ask you to ‘type in’ your mathematical relation ..
    Just think about what you’ve just said, [the largest square between 1 and k] .. that’s floor(sqrt(k)) with a different phrasing.
    Interviewers aren’t usually that sick, to the extent they would refuse such answer and insist on an instant mathematical relation ..
    As I said, it’s all about how you reached that solution, how you tackled the problem .. that’s all 😀

    AlaaShaker

    September 3, 2008 at 1:53 pm

  3. Hey, cool tips. Perhaps I’ll buy a glass of beer to the man from that forum who told me to go to your site 🙂

    Jane Goody

    April 22, 2009 at 8:46 am


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: