Tuesday, December 15, 2009

Finding whether a number is blessed or not

Problem

1,2,3,4,5,6,....

initialize
Jump=2
then 2,4,6,8,.......

remaining 1,3,5,7,9,11,.......

Jump=3
then 5,11,..........gets removed

remaining: 1,3,7,9,13,15

We carry on for jump infinitely here 1.3 are blessed as they will not be removed. Now, given a number n propose a algorithm to find out whether it is blessed number or not.

Solution :
#include
int counter = 2;
int isBlessed(int k)
{
//printf("k = %d counter = %d\n",k,counter);
if(k< counter) return 1;

if(k%counter == 0)
{
return 0;//it's not blessed
}
else
{
k = k - k/counter;
++counter;
return isBlessed(k);
}
}


int main()
{
int i;
for(i=0;i<25;i++)
{
counter = 2;
if(isBlessed(i))
printf("%d is blessed\n",i);
else
printf("%d is not blessed\n",i);
}
}

No comments:

Blog Archive