Imagine there are 1000 switches, numbered from 1 to 1000 and lined up sequentially in a single row on a very long wall. Each switch controls a light bulb on top of the switch and all the switches are at the "OFF" position in the beginning.

Then imagine there are 1000 people, each wearing a number tag, and the numbers run from 1 to 1000.

The sequence of actions are:

Starting from the person with the number 1, each person in order of their number goes from switch number 1 to switch number 1000, and flick the switches that has the numbers that are multiples of the person's number.

Here's how it would have gone:

The person number 1 goes from switch number 1 to switch number 1000, and turns on every switch. (Since his number is 1, so every switch number is a multiple of 1).

The person number 2 goes from switch number 1 to switch number 1000, and turns off all the switches with numbers that are multiples of 2, ie, 2,4,6,.....1000. (Since the 1st person turned on all the switches, the second person then turns off all the even number switches).

The person number 3 then turns switch number 3 off (initially turned on by peron number 1), turns switch number 6 on (initially turned on by person number 1 then turned off by person number 2), switch number 9 off.....

.

.

.

.

Person number 1000 simply go to switch number 1000. If it is on, he turns it off, it it is off, he turns it on.

The question is, by the end of the whole exercise, how many light bulbs are lit?

This was a question given to me on my job interview...

- Roy

## Bookmarks