Re: Algorithm to find break in contiguity

On Mon, 29 Jan 2007 19:48:03 -0500 (EST), "Arthur J. O'Dwyer"
<ajonospam@xxxxxxxxxxxxxx> wrote:


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?

Unfortunately you (Richard) snipped relevant text. Your comment is
irrelevant. Don't feel bad - I made the same mistake until I read
Arthur's comment.


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.)

From his last paragraph it is quite clear that he is talking about the
data being in order. Upon reflection I am inclined to take the view
that his interpretation is correct; the OP phrased the problem as a
break in contiguity. The thing is, we are so used to this chestnut that
we overlook a difference in wording.



.

Relevant Pages

  • Re: Algorithm to find break in contiguity
    ... save any significant time by jumping around doing a binary search, ... don't depend on how the original data is supplied), ... would make a decent followup puzzle, if an interviewer did decide ... to ask the original puzzle. ...
    (comp.programming)
  • Re: Sum Thing to Do
    ... Richard Heathfield wrote: ... >> Carl G. ... > Below is a partial spoiler, which I am confident I could extend but it's way ... > puzzle can be solved in similar vein. ...
    (rec.puzzles)
  • Re: qwyzzle level 39
    ... >> Richard Heathfield wrote: ... It is a puzzle which is open to all. ... rec.puzzles instead of the official forum. ... I also believe that you get much more satisfaction from completing this type ...
    (rec.puzzles)
  • Re: Dear Friends, do you know this puzzle, his history and solution?
    ... do you know this puzzle, his history and solution? ... Richard Heathfield ...
    (rec.puzzles)
  • Re: Dear Friends, do you know this puzzle, his history and solution?
    ... i am sorry if you read my sentences like insulting! ... tecnical preparation', just this, and this is not a insult in my BAD ... i don't know this puzzle, i have write for know ... Richard Heathfield ...
    (rec.puzzles)