Now, consider the following simple algorithm for this problem:

Find$-$Index$-1($A$[1$ : n$])$:

$$ Let i $=1.$ While A$[$i$]$ mod $5=0,$ sample i in $\{1,...,$ n$\}$ uniformly at random. Output i$.$

The proof of correctness of this algorithm is straightforward and we skip it in this question.

$($c$)$ What is the worst$-$case expected running time of Find$-$Index$-1($A$[1$ : n$])?$ Remember to prove your

answer formally. $(7$ points$)$

Solution. Solution to the part c$)$ goes here