/*Program to varify B'day paradox
 * Author :rahule@iitk.ac.in
 */


#include<stdio.h>
float min_n(void);	//function to calculate minimun number of n needed to have a 50% probability that two persoans have same B'day
int check(int n);	//function creates a random set of n B'days,and checks whethr any of them repeats or not
main()
{
  int seed,n,i,cnt=0;
  printf("\neEnter a random integer for seeding :");
  scanf("%d",&seed);
  srand(seed);
  n=min_n();	//calculates the value of n
  printf("\ncreating 100 random sets ..");
  for(i=0;i<100;i++)
    cnt=cnt+check(n);	//calculates among 100 sets of n B'days,how many sets have B'days repeating
  
  printf("\nAmong 100 random sets,%d sets were found to have atleast one date repeated!",cnt);
  
}
float min_n(void)
//function to calculate minimum  n for which the set will have an element repeating with atleast 55% prob
{
  float p=1,x=366,n;
  while( p>.5)
  {
    x--;
    p=p*(x/365);
  }
  n=365-x+1;
  return(n);
}
  
int check(int n)
//function which randomly creates a set of n B'days and calculates whether any B'day is repeating or not.If a B'day is repeated,function returns 1,else returns 0
{
  int sample[365],i,j;
  for(i=0;i<n;i++)
    sample[i]=rand()%365+1;
  for(i=0;i<n;i++)
    for(j=i+1;j<n;j++)
    {
      if(sample[i]==sample[j])
	return(1);
    }
  return(0);
}