Question : Given n number of people we have to find the expected value of total number of distinct birthdays

source : https://www.youtube.com/watch?v=U_h3IjreRek&t=120s (time stamp : 34 : 38)

Actual Answer :

expected value = 365 * (1-(364 / 365) ^ n)

My Logic :

i : total number of same same birthdays probability that there are i same birthday's -> p1 = (1 / 365) ^ (i-1) * (ways of choosing i people out of n => nCi)

now remaining n-i; i should have different birthdays so probability that n-i i will have different birthdays is

p2 = (364 / 365) * (363 / 365) .. (364-(n-i-1)) / 365

expected value is

f(x) * x, where (f(x) is the value, and x is prob of that event)

expected value is sum of (n-i+1) * p1 * p2, for i from 2 to n + the additional case where all birthdays are distinct

My logic gives accurate answers for small values of n, but gives very different results as n is increasing, Can anyone tell what's the issue with my logic or code, I am unable to figure out on my own

Code :

long double ncr(int n, int r) { if (r > n) return 0; if (r == 0 || r == n) return 1;

long double res = 1;
for (int i = 1; i <= r; i++) {
    res = res * (n - r + i) / i;
}
return res;

}

int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL);

int t;
cin >> t;
while (t --){
    int n;
    cin >> n;
    long double my_answer = 1;
    for (int i = 1; i <= n; ++ i){
        my_answer *= (long double)(365 - i + 1) / 365;
    }
    my_answer *= n;
    for (int i = 2; i <= n; ++ i){
        long double val = (n - i + 1) * ncr(n, i) * pow((long double)1 / 365, i - 1);
        int cnt = 0;
        for (int j = i + 1; j <= n; ++ j){
            val *= (long double)(365 - ++ cnt) / 365;
        }
        my_answer += val;
    }
    long double actual_answer = 365 * (1 - pow((long double)364 / 365, n));
    cout << my_answer << "\n" << actual_answer << "\n";
    cout << abs(my_answer - actual_answer) << "\n\n";
}

}

Results for N = 1 -> 30

my answer

actual answer

difference in answer

n : 1

1

1

7.80626e-18

n : 2

1.99726

1.99726

8.78204e-18

n : 3

2.99179

2.99179

8.89046e-18

n : 4

3.98355

3.98359

4.49132e-05

. . .

n : 28

20.3702

26.9886

6.61839

n : 29

20.2953

27.9146

7.61934

n : 30

20.1374

28.8381

8.70077

I was trying to solve the problem, find Euler path / circuit of an undirected graph if it exists

link : https://www.codingninjas.com/studio/problems/euler-path_1214547?leftPanelTabValue=PROBLEM

I was reading this tutorial from cp algorithms,

https://cp-algorithms.com/graph/euler_path.html

where they use adjacency matrix to find the next adjacent node or edge that has not been marked / removed, in the tutorial they mention that we should use adjacency list to store adjacent nodes to achieve time complexity of O(M)

But how will we remove edges in O(1) we can remove an adjacent node v, from the adjacency list of u in O(1) but how to remove u from adjacency list of v, for example if the the current node is u, then to remove an adjacent node we can do v = adjacency_list[u].pop_back()

but now to remove u from the adjacency list of v, we need O(N) time or LogN time if we use set, is there any way to achieve this in O(1) ?

Q: Given an array of n integers, find the sum of value of GCD for all possible pairs.

2 <= n <= 10 ^ 5

1 <= a[i] <= 10 ^ 5