Light, More Light
So, for these, I’ll post the title of the problem as the title, the description below, maybe some observations, and then finally a read more link with the solution I came up with.
From Programming Challenges (PC/UVa IDs: 110701/10110) :
There is man named Mabu who switches on-off the lights along a corridor at our university. Every bulb has its own toggle switch that changes the state of the light. If the light is off, pressing the switch turns it on. Pressing it again will turn it off. Initially each bulb is off.
He does a peculiar thing. If there are n bulbs in a corridor, he walks along the corridor back and forth n times. On the i-th walk, he toggles only the switches whose position is divisible by i. He does not press any switch when coming back to his initial position. The i-th walk is defined as going down the corridor (doing his peculiar thing) and coming back again. Determine the final state of the last bulb. Is it on or off?
Input
The input will be an integer indicating the n-th bulb in a corridor, which is \(\le 2^{32} - 1\). A zero indicates the end of input and should not be processed.
Output
Output “yes” or “no” to indicate if the light is on, with each case appearing on its own line.
Sample Input
3
6241
8191
0
Sample Output
no
yes
no
So you’re given a number n, which is the number of lightbulbs, and therefore passes. On some pass i, a switch k is flipped if i divides k (no remainder). Note that the only k we care about is n. Then, for n passes, it is sufficient to find if the number of positive factors of n is even or odd. If the number of factors is even, that corresponds to an even number of flips, and therefore the light will come back to its initial state and be off. For odd, the light will be on. Now take a second and see what property all numbers with an odd number of positive factors share. Once you’ve got it, or you give up, read ahead.
