## Count Open Lockers SOLVED [Problem of the Week]

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

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

[…] here […]

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

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 HeshamSeptember 3, 2008 at 1:49 pm

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

instantmathematical relation ..As I said, it’s all about how you reached that solution, how you tackled the problem .. that’s all 😀

AlaaShakerSeptember 3, 2008 at 1:53 pm

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 GoodyApril 22, 2009 at 8:46 am