Re: searching for missing element in an array

On Fri, 30 May 2008 04:25:42 +0000, Richard Heathfield
<rjh@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.

That won't quite do. Your points are well taken and yet there is
a problem. The original states that the numbers from 1 to n are
being placed in the array randomly. Ergo the n-1 locations
somehow hold n numbers. This implies in turn that at least one
location in the array can hold more than one number. This would
be a problem for ordinary arrays but the problem statement
clearly implies that this is a special sort of array. Since all
n numbers are present (somehow!) it follows that "missing" does
not have its customary meaning of absent. What precisely that
meaning might be is open to question. An obvious answer is a
numerological interpretation, i.e., "missing" = 13+9+19+19+9+14+7
= 90, but that is not enough. Evidently some number is 90 in
disguise and we have to find out which one it is. Since we have
already established that there is a location in the array that
has two elements the question might be to be to find that
location with two elements. How to do this is problematic. My
thought is that if we can't see 90 on the front side of the array
we look at its back side.

The moral of the story is that if you don't state the problem
carefully you can get some really weird solutions.


Richard Harter, cri@xxxxxxxx
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.
.

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