100 Lockers - One puzzle a day - Puzzle Buddies

Puzzle: You are in a locker room with 100 lockers in  a row. You have keys to all the lockers. All the lockers are initially closed. You make 100 passes, you toggle ( if the door is closed you open it, if its open you close it) all the locker doors in the first pass, second time you only visit every second door and toggle it, third time you only visit every third door and toggle it and so on.

How many doors will be open after 100th pass.

Solution: There are three ways to solve this puzzle
1. Brute force
 Keep running it for all 100 passes and then count. The solution will be correct but not elegant.
2. If you try to run brute force for first few you can infer that

• 1st locker will be toggled 1 time
• 2nd locker will be toggled 2 times
• 3rd locker will be toggled 2 times
• and so on ........

This shows us that each locker will be toggled by its own factors only.
The locker can be in open state if the factors are odd.
Now we can count factors of each number from 1 to 100 and which ever are odd will result in open lockers
3. The easiest way is that only perfect squares can have odd factors. So all perfect squares can be counted and that is the answer.

So the answer is 10 and locker numbers are 1,4,9,16,25,36,49,64,81,100.

Winner: Today's winner is Kasturi