Dave's response is the right idea. A binary search can find the number of
"holes" in the set of valid results.
Here is my solution:
int getRndVal(int N, int S, int *a)
{
// We are going to return the xth valid value
int x = rnd(N-S);
// Binary search to find the number of values in a
@Don: Note that a[j] - j is the number of non-excluded responses < a[j].
Here is the algorithm I would use:
k = rnd(N - S);
if( k < a[0] )
j = -1;
else
{
Use a binary search to find the largest j with 0 <= j < S such that
a[j] - j <= k;
}
return k + j + 1;
The algorithm uses O(1) ext
