Interview Puzzles

Stack of 'must-know' interview puzzles !

Puzzle: Puzzle 100 Locker

There are one hundred  closed lockers in a hallway  A man begins by opening all one hundred  lockers  Next, he closes every second locker   Then he goes to every third locker and closes it if it is open or opens it if it is closed (e g , he toggles every third locker)  After his one hundredth pass in the hallway, in which he toggles only locker number one hundred, how many lockers are open?
0 Vote Up   |   Post Answer   |   View Solution

By  Vineet JhunJhunwala

Sangeeta Haldhar Sangeeta Haldhar   6 years ago

1,4,9,16,25,36,49,64,81,100 these will be open

Reply    2 Vote Up   0 Vote Up

Shaan Shaan   6 years ago

The number of times a door will be toggled is based on the number of divisors the locker number has. For example, door #6 will be toggled on pass 1, 2, 3 and 6. Further note that most numbers have an even number of divisors. This makes sense since each divisor must have a matching one to make a pair to yield the product. For example, 1*6=6, 2*3=6.
The only numbers that do not have an even number of divisors are the perfect square numbers, since one of their divisors is paired with itself. For example, door #9 is toggled an odd number of times on passes 1, 3 and 9 since 1*9=9 and 3*3=9.
Thus, all non-perfect square numbered lockers will end up closed and all perfect square numbered lockers will end up open.

Reply    1 Vote Up   0 Vote Up