There is a random number generator. It generates numbers between $1$ and $n$ with equal probability. What is the expected number of turns for it to generate k distinct numbers?
EDIT: My approach is to generate random numbers until I get $k$ distinct elements. Then, the answer will be the number of tries it has taken. I am not sure whether this is correct or not.
How to approach these types of questions? I need an algorithm for this.
This is a truncated coupon collector's problem. The expected number of tries to get the first distinct coupon is $\frac nn$, the second distinct coupon $\frac n{n-1}$ more and so on until the $k$th distinct coupon takes $\frac n{n-k+1}$ tries on average. Thus the expected number of tries to get $k$ distinct coupons is $$n\sum_{m=n-k+1}^n\frac1m$$