Traversing an array and counting the number of distanct number from the given elements in an array. You are given an array $A[0 \ldots n-1]$ of $n$ numbers. Let $d$ be the 
number of \emph{distinct} numbers that occur in this array. 
For each $i$ with $0 \leq i \leq n-1$, let $N_i$ be the number of 
elements in the array that are equal to $A[i]$. 
Show that $d = \sum_{i=0}^{n-1} 1/N_i$.
Consider the following algorithm: 
Step 1: Choose an integer $k$ in $\{0,1,2,\ldots,n-1\}$ uniformly 
at random, and let $a = A[k]$. 
Step 2: Traverse the array and compute the number $N_k$ of times that $a$ occurs.
Step 3:
Return the value $X = n/N_k$.  
Determine the expected value $E(X)$ of the random variable $X$. 

Suppose that the number $a$ occurs $N_a$ times. Each of the $N_a$ occurrences of $a$ makes a contribution of $\frac{1}{N_a}$ to the sum $\sum_0^{n-1}\frac{1}{N_i}$, for a total contribution of $N_a\cdot \frac{1}{N_a}=1$.  Thus the sum $\sum_0^{n-1}\frac{1}{N_i}$ counts the number of distinct $a$ in the array.
The expectation question is essentially a rewording of the above observation. The $i$ are chosen with equal probabilities $\frac{1}{n}$.  If $i$ is chosen, then $X=\frac{n}{N_i}$.  The expected value of $X$ is therefore $\sum_{i=0}^{n-1} \frac{1}{n} \cdot\frac{n}{N_i}$. Thus if there are $d$ distinct values in the array, then $E(X)=d$.  
