Coding Interview — Switching Light Bulbs

This problem has a lot of different variations, but the one we will cover here is the following:

Imagine there are 100 light bulbs, labeled from 1 to 100, lined up all set to off initially. There are also 100 people each numbered 1 to 100 as well.

Person 1 will go through all the light bulbs and flip the switch turning all of them on. Then, person number 2 will go through all the light bulbs and flip the switch on each 2nd element turning them off, namely: light bulbs #2, #4, #6, #8, etc. Then person 3 will go and do the same for the 3rd ligh bulb, 6th, 9th, etc.

Then, questions are usually asked about the light bulbs, for example:

• How many light bulbs will be on after 100 people have gone through them?
• What is the status of the Nth light bulb (34th, 62nd, etc.)? Is it on or off
• How many people need to go through the line of light bulbs until exactly K light bulbs are set to on?

Solution

To answer any of these questions, we’ll write a function that goes through all N light bulbs and performs each operation for every person labeled from 1 to N.

What we’ll do for this problem is setup an array of N elements all set to false, which will represent a light bulb in the off position.

Then we will loop through every person from 1 to N, and within that loop create another loop that will multiply each person’s number by a number each time to change the following light bulbs:

• For i = 1, change 1, 2, 3, 4, etc.
• For i = 2, change 2, 4, 6, 8, etc.
• For i = 3, change 3, 6, 9, 12, etc.

If you are interested in data engineering, check out the course below.