// Arup Guha
// 1/9/2013
// Calculates theoretical expectation for number of people we
// must ask for birthdays before we get the first repeat.
/*** This is the second version that works more efficiently. It
     reuses a portion of the previous probability calculation.
***/

#include <stdio.h>

#define N 365

int main() {

    double ans = 0;

    // Loop through each possible number of days.
    int i;

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

        // This is our updated value that we'll use to build future values of
        // i-1 people having different birthdays.
        term = term*(N-i+2)/N;

        // Multiply the previous term by the probability of the ith person matching
        // a previous person.
        double adjterm = term*(i-1)/N;

        // Add this term in to the expectation, weighted by i.
        ans = ans + i*adjterm;
    }

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

    return 0;
}