I'm trying to figure out the expected number of times this algorithm will print. I'm stuck on how to go about doing so. I used an indicator variable to keep track of the number of print statements being printed, but I'm stumped on the meat part of it.
random(X,Y,Z):
print(X) if Y != X: print(Y) if Z != Y and Z != X: print(Z) You will suppose the inputs X,Y,Z are chosen at random, uniformly and independently from the set {1,...,k}, (for some k being >=1).
It appears, the code is printing the distinct elements of the given 3 input set.
The number of times 1 print happens = $k$ (all 3 inputs are the same).
The number of times 2 prints happens = $3k(k-1)$ (two of the inputs are the same).
The number of times 3 prints happens = $k(k-1)(k-2)$ (all the three inputs are different).
So, the expected number of times this algorithm will print would be
$\frac{1\times k + 2\times 3k(k-1)+ 3 \times k(k-1)(k-2)}{k^3}$ = $\frac{1+3k(k-1)}{k^2}$