$\newcommand\ldotd{\mathinner{..}}$Given that $A[1\ldotd n]$ are integers such that $0\le A[k]\le m$ for all $1\le k\le n$, and the occurrence of each number except a particular number in $A[1\ldotd n]$ is an odd number. Try to find the number whose occurrence is an even number.

There is an $\Theta(n\log n)$ algorithm: we sort $A[1\ldotd n]$ into $B[1\ldotd n]$, and break $B[1\ldotd n]$ into many pieces, whose elements' value are the same, therefore we can count the occurrence of each element.

I want to find a worst-case-$O(n)$-time-and-$O(n)$-space algorithm.

Supposing that $m=\Omega(n^{1+\epsilon})$ and $\epsilon>0$, therefore radix sort is not acceptable. $\DeclareMathOperator{\xor}{xor}$ Binary bitwise operations are acceptable, for example, $A[1]\xor A[2]$.

  • $\begingroup$ Aryabhata's answer below shows that the general case is not good, but perhaps you have further restrictions available? A simple (but big) restriction would be to enforce that all the entries in the array are $O(n)$ in size. This would give a pretty trivial linear algorithm. $\endgroup$ Jul 23 '12 at 4:02
  • 1
    $\begingroup$ @LukeMathieson: I deleted that answer, as I am not yet convinced that the paper I cited will work without any modification, and besides, OP seems to be interested only in the uniform cost RAM model. $\endgroup$
    – Aryabhata
    Jul 23 '12 at 4:28
  • $\begingroup$ @Aryabhata: hehe, well the answer that's not there then! Out of interesting, and perhaps useful for Frank, what did you think was the problem with adapting the result in the paper? A quick skim suggested it applied, but I obviously didn't read into it. $\endgroup$ Jul 23 '12 at 4:51
  • $\begingroup$ @LukeMathieson: The fact that the other elements need to appear an odd number of times in the current problem. Since, I skimmed over the proof too... $\endgroup$
    – Aryabhata
    Jul 23 '12 at 5:36
  • $\begingroup$ It would be interesting if you are interested in theoretic results or in practical solutions. From the theory point of view, my first quick response is, that you can sort a list of integers faster than $O(n\log n)$. There is a deterministic algorithm by Han that runs in $O(\log\log n)$ time. For randomized algorithms, even better results are known, e.g. Han and Thorup have found a $O(n \sqrt{\log\log n})$ expected time algorithm. However, I think that your problem shouldn't require sorting. $\endgroup$
    – A.Schulz
    Jul 23 '12 at 7:01

Here is an idea for a simple algorithm; just count all occurrences!

  1. Find $m = \max A$. -- time $\Theta(n)$
  2. "Allocate" array $C[0..m]$. -- time $O(1)$¹
  3. Iterate over $A$ and increase $C[x]$ by one whenever you find $A[\_]=x$. If $C[x]$ was $0$, add $x$ to a linear list $L$. -- time $\Theta(n)$
  4. Iterate over $L$ and find the element $x_e$ with $C[x_e]$ even. -- time $O(n)$.
  5. Return $x_e$.

All in all, this gives you a linear-time algorithm which may use (in the sense of allocating) lots of memory. Note that being able to random-access $C$ in constant time independently of $m$ is crucial here.

An additional $O(n)$ bound on space is more difficult with this approach; I don't know of any dictionary data-structure that offers $O(1)$ time lookup. You can use hash-tables for which here are implementations with $O(1 + k/n)$ expected lookup time ($n$ the table's size, $k$ the number of stored elements) so you can get arbitrarily good with linear space -- in expectation. If all values in $A$ map to the same hash value, you are screwed.

  1. On a RAM, this is implicitly done; all we need is the start position and maybe the end position.

An almost trivial solution - which uses however $\Theta(n)$ space - is to use a hash map. Recall that a hash map has amortized runtime $\mathcal{O}(1)$ for adding and looking up elements.

Hence, we can use the following algorithm:

  1. Allocate a hash map $H$. Iterate over $A$. For each element $i \in A$, increase the number of occurences seen, i.e. $H(i)++$.

  2. Iterate through the key set of the hash map, and check which of the keys has an even count of occurences.

Now this is a simple algorithm which doesn't really use any large trick, but sometimes even this suffices. If not, you might want to specifiy what space restrictions you impose.

  • $\begingroup$ I would still like to know, if there is a non-randomized $O(n)$ time algorithm using polynomial space. In particular, is there any theoretical evidence that finding the only even-occurring item is harder than finding the only odd-occurring item? $\endgroup$
    – A.Schulz
    Jul 23 '12 at 11:01
  • $\begingroup$ @A.Schulz I think that it is the $O(n)$-expected-time algorithm by using hash table. I remember that somebody told me an $O(n)$-algorithm (or for some special case, say, odd=1 and even=2) maybe with stack, but I cannot recall it. $\endgroup$
    – Yai0Phah
    Jul 23 '12 at 12:11
  • $\begingroup$ Not every hashtable implementation has this property; usually, lookup is not $O(1)$, not even amortized (afaik). In fact, a prior discussion has not yielded any implementation that has constant time lookup. Can you be more specific? $\endgroup$
    – Raphael
    Jul 23 '12 at 15:21

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.