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.
So, the idea is that most numbers have an even number of positive factors. Take 6 for instance: \(1 \times 2 \times 3 \times 6\). The only way for a number to have an odd number of positive factors is for the middle factor to be the square root of the number, as is the case with 16: \(1 \times 2 \times 4 \times 8 \times 16\). This implies that, to determine if the light is on or off, it is sufficient to just determine if the number is a perfect square. Easiest way to do that is to see if the square root of the number is an integer. Now, in most languages, square root isn’t a precision operation, so you’ll want to do something like:
long f = (long) (sqrt(n) + 0.5);
return (f*f == n);
I first tried another way where I kept f as a double and ensured that the difference of f and round(f) was small enough (therefore f is an integer), but in this method you don’t have to select an arbitrary precision value. The + 0.5 is unnecessary in Java for inputs up to very large values, but better safe than sorry.
