[Solved]: Checking whether all integers appear exactly once

Problem Detail: 

Let $\texttt{a[]}$ be a finite array. We want to check whether every number between $\texttt {min(a[])}$ and $\texttt {max(a[])}$ appears exactly once.

An obvious solution is sorting the array in time $O(n\log(n))$ and go through the sorted array in linear time and check that $\texttt{a[k+1] == a[k]+1}$ for $0\leq\texttt{k} < \texttt{length(a)-1}$.

The total complexity of this would be again $O(n\log(n))$. Is there a better way to do this?

Asked By : Dominic van der Zypen

Answered By : Juho

Let $A$ contain $n$ elements. Scan $A$ to determine the maximum value $m$ in $A$. Then, initialize a bit vector $B$ of size $m$ to all zeros. Then scan $A$ and use $B$ for bookkeeping: when you encounter $i$ in $A$, set $B[i]$ to one (if $B[i]$ is already set, return false). In the end, return true if and only if $B$ contains exactly $n$ ones. This algorithm runs in $\Theta(n+m)$ time, or even in $\Theta(n)$ time if we assume $m = O(n)$.

We can also be a little bit more clever with David Richerby's idea. Let us scan $A$ to find its minimum value $s$. Then initialize an array $B$, this time of size $n$, to all zeros. Go through $A$ again, and when you encounter the value $i$ in $A$: if $i - s > n$ or $B[i-s]=1$, return false. Otherwise, set $B[i-s]=1$. Obviously, this algorithm runs in $\Theta(n)$ time (independent of $m$).

In both cases we assume reading the index of an array is done in unit time, and also that arbitrary width arithmetic is performed in unit time.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/40355