Comment by vitus
1 year ago
The stated inputs are integers between 1 and 100,000, so if you're generating 1 million inputs, then you have 0.99999 ^ 1e6 = 4.5e-5 chance (roughly e^-10) of missing any given number, or roughly double that for missing any pair of values.
The key observation here is that you're sampling a relatively small space with a much greater number of samples, such that you have very high probability of hitting upon any point in the space.
Of course, it wouldn't work if you considered the full 32-bit integer space without increasing the number of samples to compensate. And, you'd need to be a little more clever to compute the largest possible value in your range.
Indeed. My understanding is that people ask this sort of thing in interviews specifically to see if you notice the implications of restricting the input values to a narrow range.