Re: searching for missing element in an array

Bartc said:


"Richard Heathfield" <rjh@xxxxxxxxxxxxxxx> wrote in message
news:WJSdnRXXlf9Xxd3VnZ2dneKdnZydnZ2d@xxxxxxxxx
user923005 said:

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

An array of all 1's could also fit the description. Each 1 is in the
range 1 to n.

But then there would be more than one number missing, whereas we are
explicitly told that exactly one number is missing (because the spec reads
"which number is missing", not "which numbers are missing"). I already
explained this once.

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