An Interesting Problem

The Problem

There is man named "mabu" for switching on-off light in our University. He switches on-off the lights in a corridor. Every bulb has its own toggle switch. That is, if it is pressed then the bulb turns on. Another press will turn it off. To save power consumption (or may be he is mad or something else) he does a peculiar thing. If in a corridor there is `n' bulbs, he walks along the corridor back and forth `n' times and in i'th walk he toggles only the switches whose serial is divisable by i. He does not press any switch when coming back to his initial position. A i'th walk is defined as going down the corridor (while doing the peculiar thing) and coming back again. Now you have to determine what is the final condition of the last bulb. Is it on or off?

The Input

The input will be an integer iandicating the n'th bulb in a corridor. Which is less then or equals 2^32-1. A zero indicates the end of input. You should not process this input. The Output Output "yes" if the light is on otherwise "no" , in a single line.

Sample Input

3
6241
8191
0

Sample Output

no
yes
no

I came across this problem during a programming contest. Although the lengthy problem statement can confuse, it is really straightforward. You are given number n. All you have to do is check whether n has an even number of divisors or odd. If even, you print "no" otherwise you print "yes".

A Naive Implementation:-
for i = [1,n]
…if n is divisible by i
……..count = count + 1
if count is even
…print no
else
…print yes

This was what struck me initially. However, I got a "Time Limit Exceeded" from the online compiler. Repeated efforts to optimize were all futile.

So it became clear, that I must design an algorithm markedly better than the naive one shown above. It took me a while ....

Well, what I finally did was this…. Check if n is a perfect square. If yes, the print “yes”, else print “no”. The proof follows.

Assume n is not a perfect square. We can see that when n is represented as a product of two numbers, one among m would be lesser than √n and the other would be greater than √n.

Consider the set of divisors of n. Let us say that there are x divisors of n below √n. Now, each of these x divisors would give an unique and different dividend when they divide n. We can see that the set of these dividends are indeed the set of divisors of n which are greater than √n. So this means that for every multiple pair, there is another multiple pair, which is just the reverse. Thus, we can say that the multiple-pairs themselves occur in pairs, which leads to the conclusion that the number of divisors for a non-perfect square number is even.

ILLUSTRATION

28 = 1 * 28
= 2 * 14
= 4 * 7
= 7 * 4
= 14 * 2
= 28 * 1

There are six multiple-pairs of 28. Among the six, three of them are unique and the other three are just mirror images.

Now, for a perfect square, the same argument would hold good. But there is the extra pair of √n * √n = n. This is the only other pair, so finally the number of divisors are odd.

So now our final algorithm would look like this.

if n is a perfect square
….print yes
else
….print no

Moral of the story:- Analogous to "Think before you ink", we have "think before you bang away on your keyboard"...

Broken Wings - Kahlil Gibran

I had never really been moved by "romantic" movies or songs or poems. However, this book changed all that! Very unlike the other normal love stories, Broken Wings embraces the idea of unconditional love. It is redolent with images. Kahlil Gibran is truly a genius.

I would recommend this book to everyone. You can download it here. Small book, but trust me each line would hold your attention and make you think. I have seen quite a few people pride themselves saying "I do not like romantic mushy love stories. They are boring ...." Mostly Men... And some who consider love as a sign of weakness, and something unscientific. I was one of them!

Though I still do not seek out such stories/works, I enjoy them when I stumble upon them. This book, if read with an open mind, will cause even the coldest and shrewdest person to view love as a mystery. Try it. You will be defeated!!!