Re: searching for missing element in an array

user923005 said:

On May 29, 9:25 pm, Richard Heathfield <r...@xxxxxxxxxxxxxxx> wrote:
user923005 said:

On May 29, 4:45 pm, CBFalconer <cbfalco...@xxxxxxxxx> wrote:
user923005 wrote:
rossum <rossu...@xxxxxxxxxxxx> wrote:

<snip>

The difference is the missing number.

What happens if you have some number twice? e.g.: 1,2,2,4,5
What happens if the array was initialized to all -1 values? Do
we know that a zero is stored in the slot of the missing number?

Read the first paragraph quoted, the original statement of the
problem.

The original problem statement makes not statement about the
initialization of the array. In no place does it say that all the
initial entries are zero.

On this occasion, I recommend (and I must admit that this comes as a
surprise) that you listen to Chuck. The original problem statement
nullifies your objections completely. Here it is again:

"Suppose we have n numbers(from 1 to n) and there is an array of size
n-1. How can we find, which number is missing from the array if
numbers 1 to n are being placed in array randomly."

From the phrase "which number is missing" we deduce that precisely one
number is missing. If duplicates were allowed (and also if "number" were
allowed to include non-integers, which I mention only in an attempt at
completeness), more than one number might be missing. Since it is known
that precisely one number is missing, we deduce that duplicates are not
allowed. Furthermore, because we know that only one number is missing
and there are n numbers (all in the range 1 to n) originally, we know
that there are n-1 numbers present. Since the array has size n-1, we can
legitimately and correctly deduce that it is entirely populated with n-1
unique numbers in the range 1 to n.

"The trick" is therefore guaranteed to work provided only that n(n-1)/2
does not exceed the maximum possible value for a number on the host
system.

I completely disagree.
An array initialized with -1 or with INT_MAX would also fit the
initial description.

I agree that the array could be initialised with -1 or INT_MAX or any other
number you care to mention, but this makes no difference because all those
values are known to be overwritten by values in the range 1 to n, for the
reason I stated above.

I think it is a mistake to assume specification details that are
definitely not stated.

I think the spec is perfectly clear. The English is a little shaky, it's
true, and it could conceivably be twisted into a meaning that the OP
didn't intend, but I suspect that English is probably not the OP's first
language, so I'd be inclined to cut him a little slack for that. The most
obvious reading is isomorphic to having n ping-pong balls labelled 1
through n, and n-1 buckets, and you put exactly one of your n ping-pong
balls into each bucket - the puzzle is to work out, as fast as possible,
which ball you have left over, without looking at it directly.

If the OP meant something that isn't isomorphic to that, I'd be very
surprised indeed.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
.

Relevant Pages

  • Re: searching for missing element in an array
    ... What happens if the array was initialized to all -1 values? ... we know that a zero is stored in the slot of the missing number? ... initialization of the array. ... there are n-1 numbers present. ...
    (comp.programming)
  • Re: searching for missing element in an array
    ... What happens if the array was initialized to all -1 values? ... we know that a zero is stored in the slot of the missing number? ... The original problem statement makes not statement about the ... there are n-1 numbers present. ...
    (comp.programming)
  • Re: question about max_readahead for ide devices in 2.4?
    ... Andrew> That's correct - it's all a bit weird. ... sets an entry in the read_aheadarray. ... Or am I missing something else?? ... send the line "unsubscribe linux-kernel" in ...
    (Linux-Kernel)
  • Re: array Puzzle (spoiler)
    ... >) The key is that the integers in the input array are sequential, ... > So now you know one value, and the sum of the two others. ... some of the missing values is generally applicable. ... None of these ranges can contain *all* of the missing values, ...
    (comp.programming)
  • Re: searching for missing element in an array
    ... "Suppose we have n numbersand there is an array of size ... which number is missing from the array if ... there are n-1 numbers present. ... which is implied by the phrase "which number is missing" ...
    (comp.programming)
Quantcast