# Thread: One More (sry forgot i also skipped this one to hard for me :P)

1. ## One More (sry forgot i also skipped this one to hard for me :P)

You are given an array A[0....n-1] of n numbers. Let d be the number ofdistinct numbers that occur in this array. For each i with 0 <=i <=n-1 let Ni be thenumber of elements in the array that are equal to A[i].  Show that d= summation i=0 n-1 1/NiConsider the following algorithm:Step 1: Choose an integer k in{0,1,2,......n-1} uniformly at random, and let a = A[k].Step 2: Traverse the array and compute the number Nk of times that a occurs.Step 3: Return the value X = n/Nk.Determine the expected value E(X) of the random variable X.

I'm pretty sure that you are suppose to use the definition of expected value. But not 100% sure :S

2. ## Re: One More (sry forgot i also skipped this one to hard for me :P)

for each unique element in the alphabet $\dfrac{1}{N_i}$ appears in the sum $N_i$ times. Thus the sum is equal to the size of the alphabet, i.e. d.