Light More Light, UVa — 10110

Try it yourself on UVa. It’s Fun!

This problem has also been part of the programming challenges on the Algorithm Design Manual’s chapter 2.

The Premise

The premise of the problem can be chalked out like this way:

• A guy goes along corridor N times which have N bulbs
• Every time he goes along the corridor he toggles the switch of certain bulbs based on certain condition
• We have to determine the state of the last bulb i.e. Nth bulb.

The Conditions

The conditions are as follows:

• The bulbs have serial numbers starting from 1 to N i.e. the first bulb = 1, second = 2 and Nth bulb’s serial is N
• At each iteration, we only consider one go, not the return journey by that guy.
• At the ith iteration, he only toggles the switch of the bulb whose serial number is divisible by i. Or in other words, any bulb with serial number N, will be toggled exactly Z number of times, where Z = the number of positive factors of N
• We have to output, YES => the Nth bulb is ON, NO => the Nth bulb is OFF
• Initially, all the bulbs are turned OFF

The Idea

• The idea to solve the problem is in grasping the notion that, we are essentially trying to find the number of positive factors of the Nth number.