Re: Algorithm to find break in contiguity


On Mon, 29 Jan 2007, Richard Heathfield wrote:
robert maas, see http://tinyurl.com/uh3t said:
From: use...@xxxxxxxxxxxxxxx
I need an efficient algorithm for the following problem:
If you have unique N-1 numbers in the range 1 to N, find the
missing number.

What's best depends almost entirely on how your original data is
given to you. If it's stored in a disk file, you probably can't
save any significant time by jumping around doing a binary search,

Given that two O(n) solutions have already been given elsethread (which
don't depend on how the original data is supplied), why would he want an
O(n log n) solution anyway?

Robert didn't spell out all of his assumptions, but I think his
observation was that if somebody else has done the sorting for you
already, then you can find the missing number in just O(lg n) by
using the same pattern you'd use to do a binary search:

if (array[i] == i)
step right
else /* array[i] == i+1 */
step left

Now, the OP didn't say the data was sorted, and if it were sorted,
that would make the whole scenario even more implausible than it
already is. But IMHO "What if it's sorted?" (and Robert's answer)
would make a decent followup puzzle, if an interviewer did decide
to ask the original puzzle.
(Not that I'm advocating the asking of trivial puzzles in
interviews, mind you.)

-Arthur
.