Given a string of length $n$ over an alphabet $[m]$ where $n > m$, we
consider the problem of finding a repeated element in a single
pass. We given a randomized algorithm for this problem that uses
$O((\log m)^4)$ space. This is the first sub-linear space one-pass
algorithm for this problem, answering a question raised by
Muthukrishnan and Tarui \cite{Muthu-survey, Tarui}.

In contrast, we show that any deterministic one-pass algorithm for finding 
a
repeated element needs space $\Omega(m)$, even if $n$ is arbitrarily
larger than $m$. However, we show that when we have access to a clock
that records the current position in the stream, there is a
deterministic algorithm using space $\log m + O(1)$ if $n \geq 2^m$;
thus for this problem non-uniformity adds considerable power to
deterministic algorithms.