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.