6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I am confused. a) "random access" does not imply "randomization". What do you really mean here? b) Do you want exact algorithms? c) Please clarify which runtime is to be achieve with streaming algorithms (how many passes are allowed?) and which with conventional ones. d) What does "$\log_2 n$ bit numbers" mean: $\log_2 n$ numbers or $\log_2 n$ bits? $\endgroup$ – Raphael Jun 3 '12 at 12:26
  • $\begingroup$ $O(1)$ is very hard to reach. For example, storing the position of a cell (i.e. an integer between $1$ and $n$) takes $⎡\log_2n⎤$ bits. $\endgroup$ – jmad Jun 3 '12 at 20:30
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.