Re: searching for missing element in an array

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.

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