// Arup Guha
// 1/9/2013
// Calculates theoretical expectation for number of people we
// must ask for birthdays before we get the first repeat.
/*** About as efficient as bdayexp2, but uses more memory and should
     be a bit easier to understand.
***/

#include <stdio.h>

#define N 365

int main() {

    // Pre-calculate all of these common terms. term[i] stores the probability
    // that i-1 people all have different birthdays.
    double terms[N+2];
    terms[2] = 1;
    int i;
    for (i=3; i<=N+1; i++)
        terms[i] = terms[i-1]*(N-i+2)/N;

    double ans = 0;

    // Loop through each possible number of days.

    for (i=2; i<=N+1; i++) {

        // We multiply in the probability of the last person having a matching bday.
        // We look up the appropriate probability in the array terms.
        double term = terms[i]*(i-1)/N;

        // Add this in...
        ans = ans + i*term;
    }

    // Voila, our answer!
    printf("Expected number of days = %lf.\n", ans);

    return 0;
}