CareerCup

can you please elaborate further. List is a linked list or just a pool of numbers.

Search for Reservoir sampling

Example: N1->N2->N3->N4

Iterate through list from beginning
- Start by choosing between N1 and N2 with a 1/2 chance of picking either one.
- Then pick between ResultOf(N1,N2) and N3 with a 1/3 chance of picking N3 and 2/3 chance of picking ResultOf(N1,N2)
- Then pick between ResultOf(N1,N2,N3) and N4 with a 1/4 chance of picking N4 and 3/4 chance of picking ResultOf(N1,N2,N3)

Solution:
- Keep choosing between previousChoice and NewChoice with a 1/N chance of picking NewChoice and (N-1)/N chance of picking previousChoice where N is the Node number

Proof: If you go thorough the above example, N1 was chosen with a chance of (3/4)(2/3)(1/2)=(1/4)

#include<stdio.h>
int main()
{
int r=0,n=0,sum=0;
scanf("%d",&n);
while(n)
{
r=n%10;
sum=sum+r;
if(sum>9)
sum=sum-9;
n=n/10;
}
printf("%d",sum);
return 0;
}

If we know the length of the list and can access any element at will, then just take list[rand(length)].

If we know the length of the list but cannot access every element at will (e.g. linked list?, or stream), then produce k=rand[length] and traverse the list until you get to the k-th element.

If we don't know the length of the list and cannot access its elements at will, then create a variable X, write the first element of the list to X, swap with the second element with probability 1/2, swap with the third element with probability 1/3, and so on. At the end, return X. One can prove by induction that this returns a uniformly random element from the list.