carraysrandom

Finding the probability of occurrence N people having the same birthday


I have a homework with regards to finding the number of occurrences where N people have the same birthdays. I have to write a function findSameBirthday that takes as argument the birthdays array and the value K. The function returns true if there is an occurrence of K similar birthdays within the N elements. I have generated an array called birthdays, which is filled with numbers from 0 to 364. However, when I run my code, I do not seem to get an output. Where have I gone wrong?

My idea to check for the same birthdays in an array is:

  1. From birthdays[0], I will check it with birthdays[1], birthdays[2], birthdays[3], ..., birthdays[999].
  2. From birthdays[1], I will check it with birthdays[2], ... , birthdays[999].
  3. For each successful find, I will increase hit by 1.
  4. Hence, as long as hit is 1 or more, I will return true, else I will return false from the function findSameBirthday.

This is my code; it's also here: http://codepad.org/JFLvUn4w

  #include <stdio.h>
  #include <stdbool.h>
  #include <stdlib.h>
  #include <time.h>
  #define SEED time(0)
  #define MAX 1000

  void fillBirthdays(int birthdays[], int N);
  bool findSameBirthday(int birthdays[], int k);

  int main(void)
  {
      int birthdays[MAX]={0};
      int hits=0, k=0, N=0;

      scanf("%d", &N);
      srand((unsigned int) SEED);
      fillBirthdays(birthdays, N);
      findSameBirthday(birthdays, k);
      printf("%d", hits);

      return 0;
  }

  /*  
      fillBirthdays fills N birthdays into the array birthdays
      by using a table-lookup method.  The indices 0 to 364
      represent the different birthdays, and the value of 
      birthdays[k] is the number of people within the group of N
      having the same birthday k.

  Precondition: none.
   */
  void fillBirthdays(int birthdays[], int N)
  {
      int i=0;

      for(i=0;i<N;i++)
      {
          birthdays[i]=rand()%365;
      }

      return;
  }

  /*  
      findSameBirthday returns true if there are k (or more)
      same birthdays, and false otherwise.

  Precondition: none.
   */
  bool findSameBirthday(int birthdays[], int k)
  {
      int N=0, i=0, j=0, hits=0;
      bool samebirthday=true;

      for(i=0;i<N;i++)
      {
          for(j=1;j<N;j++)
          {
              if(birthdays[i]==birthdays[j])
                  hits=hits+1;
          }
      }
      if(hits>0)
          return samebirthday;
      else
          return false;
  }

Solution

  • This should fix your findSameBirthday function:

    /* findSameBirthday returns true if there are k (or more)
       same birthdays, and false otherwise.
    
       Precondition: none. */
    bool findSameBirthday(int birthdays[], int k)
    {
        int hits = 0;
    
        /* We don't know how big the array is, but that's ok,
           loop to max but break out early if needed. 
           birthdays array is 0 initialized so will be filled 
           with 0's where no data is present. */
        for (int i = 0; i < MAX; i++)  
        {
            if (!birthdays[i]) {break;}     // We have reached the end of the array, break out
                                             // And check hit count
            for (int j = i+1; j < MAX; j++)  // Start from i+1 so there is no overlap
            {
                if (!birthdays[j]) {break;} // We have reached the end of the array, break out 
                                            // And check next number
                if (birthdays[i] == birthdays[j])
                    {hits++;}
            }
        }
        return hits >= k; // >= means equal or more
    }
    

    You could of course pass N into the function too. You can then remove the checks and the breaks in the loops, but I wanted to match your function declaration.

    /* findSameBirthday returns true if there are k (or more)
       same birthdays, and false otherwise.
    
       Precondition: none. */
    bool findSameBirthday(int birthdays[], int N, int k)
    {
        int hits = 0;
        
        /* We don't know how big the array is, but that's ok,
           loop to max but break out early if needed. 
           birthdays array is 0 initialized so will be filled 
           with 0's where no data is present. */
        for (int i = 0; i < n; i++)  
        {
            for (int j = i+1; j < n; j++)  // Start from i+1 so there is no overlap
            {
                if (birthdays[i] == birthdays[j])
                    {hits++;}
            }
        }
        return hits >= k; // >= means equal or more
    }   
    

    You understand that with an input like this:

    int birthdays[] = {5, 5, 2, 7, 5, 9, 5};
    

    The result with this algorithm will be sum(0 to n-1) where n is the number of people who share the same birthday?
    (in this case the result will be 6).

    as for why you are not getting any output, you should (currently) be seeing a 0 output (see here). This is because you set hits in main to be 0 and do not modify it.

    If you want it to just say that there are 'k' matching birtdays or not, you can change the end of main() to be:

    //findSameBirthday(birthdays, k);
    printf("%s", findSameBirthday(birthdays, k)?
           "No. of matching Birthdays hits threshold":
           "No. of matching Birthdays does not hit threshold"
    );
    

    If you want to output the number of hits:

    • Change function prototype of findSameBirthday to int findSameBirthday(...)

    • Return hits from findSameBirthday()

    • In main:

      hits = findSameBirthday(birthdays, k);
      printf("Number of matching birthdays found: %d", hits);
      

    This will output the number of hits.