/* Program to implement josephus problem */
#include
#include
#define new (node *)malloc(sizeof(node))
struct link
{
int info;
struct link *next;
};
typedef struct link node;
void create(node **h,int n)
{
int x=0;
char ch;
node *c=*h;
do
{
//printf("\nEnter data : ");
c->info=rand()%100;
x++;
if(x==n)
break;
c->next=new;
c=c->next;
}while(x!=n);
c->next=*h;
}
void display(node **h)
{
node *c=*h;
printf("\nList : ");
while(c->next!=*h)
{
printf(" %d --> ",c->info);
c=c->next;
}
printf(" %d --> ",c->info);
printf("\b\b\b\b ");
printf("\n\n");
}
int joseph(node **h,int n,int x,int cnt)
{
node *c=*h,*p;
int i=1;
while(c->next!=*h)
{
if(c->info!=x)
{
p=c;
c=c->next;
}
else break;
}
while(c!=p)
{
if(i%cnt==0)
{
p->next=c->next;
free(c);
c=p->next;
}
else
{
p=c;
c=c->next;
}
i++;
}
int w=c->info;
return w;
}
main()
{
int n,cnt,x;
printf("\nProgram to implement Josephus Problem : \n");
node *h;
h=new;
printf("Enter the number of elements : \n");
scanf("%d",&n);
printf("\nTo insert in the list : ");
create(&h,n);
printf("\nInitial list : \n");
display(&h);
printf("\nEnter the element from which count begins : \n");
scanf("%d",&x);
printf("Enter count : \n");
scanf("%d",&cnt);
int w=joseph(&h,n,x,cnt);
printf("\nWinner : %d ",w);
printf("\n\n");
}
