lundi 26 octobre 2020

Expected numbers of turns to generate k distinct elements [closed]

Alice got a random number generator, The random number generated is between 1 to n equiprobably. Now alice wants to know the expected number of turns to generate k distinct numbers. Return the answer modulo 10^9 + 7. I only have constraints for this. No sample input and output. 1<=k<=n <= 10^5

EDIT: My approach is to generate random numbers till I get k distinct elements and the answer will be the number of tries it had taken. I doubt whether this is correct or not.

How to approach these types of questions? Need algorithm for this.




Aucun commentaire:

Enregistrer un commentaire