Streaming algorithm and random access

Consider an array $X$ of $n$ cells, each containing a number from $\{1,..., n\}$. There is at least
one duplicate number, i.e., a number that appears at least twice. I want output some duplicate number. When streaming we may pass over $X$ more than once. The inspection of a cell generates cost $1$. The cost of a run of an algorithm is the sum of all individual costs. I can at most store $\log_2n$ bit numbers.
I tried to do that with a streaming algorithm that uses additional memory $O(1)$ with costs $O(n^2)$. Is it possible to state a ramdom access algorithm that uses additional memory $O(\log_2n)$ with costs $O(n)$?.

Which algorithm solves the problem by using additional memory $O(1)$ with costs $O(n^2)$?.
Which algorithm solves the problem by using additional memory $O(\log_2n)$ with costs $O(n)$?.

My problem is similar to the cycle detection problem, but I don't know how to use the cycle detection problem to solve mine. Is there maybe a simpler way that I can't see now?

Here's how to reduce your problem to cycle detection. Your array is a mapping $f$ from $[n]$ to $[n]$. From each starting point $x$, you can iterate $f$. Using a cycle detection algorithm, you can either find out that the iterates of $x$ form a cycle, or find two iterates that map to the same point (your duplicate). For some starting point, you will find a duplicate.

StackExchange Computer Science Q#2199, answer score: 2