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:
birthdays[0]
, I will check it with birthdays[1]
, birthdays[2]
, birthdays[3]
, ..., birthdays[999]
.birthdays[1]
, I will check it with birthdays[2]
, ... , birthdays[999]
.hit
by 1.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;
}
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.