Finding one of 2/3 of all array elements in constant expected time
One approach would be to randomly pick a large constant $k$ indices and test them. The exact probability of at least one of them being $A[i] = X$ would be:

$$\begin{align}
P(\text{at least }1\; X) &amp;= 1 - P(\text{all are } Y)\\
&amp; = 1 - \left(\frac{n/3}{n}\cdot \frac{n/3-1}{n-1}\cdot \ldots \cdot \frac{n/3 - (k-1)}{n - (k-1)}\right)\\[0.5em]
&amp; \geq 1 - 3^{-k}
\end{align}$$
This inequality holds as $n$ approaches $\infty$ for some constant $k$ because:
$$\lim_{n\to\infty} \frac{n/3 - k}{n - k} = \frac{1}{3}$$
Even for some small $k$ like 10, the probability of finding an index $i$ such that $A[i] = X$ is:
$$\begin{align}
P(\text{at least }1\; X) &amp;\geq 1 - 3^{-10}\\
&amp; \geq 0.99998
\end{align}$$