Re: searching for missing element in an array


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

--
Bartc


.

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)