Re: searching for missing element in an array

Richard Harter wrote:
On Fri, 30 May 2008 04:25:42 +0000, Richard Heathfield
<rjh@xxxxxxxxxxxxxxx> wrote:

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.

It says "numbers 1 to n are being placed in array randomly". It does
not say "*the* numbers 1 to n". Because of the lack of a definite
article, I interpret "numbers 1 to n" as meaning "numbers chosen from
the range 1 to n". This is a reasonable interpretation, and it jibes
with the further information that there there is exactly one number
missing, which is implied by the phrase "which number is missing"
having the singular form of "number".

So, while it could've been phrased better so that less work was
required to understand it, I think it's pretty unambiguous what
the problem statement is.

- Logan
.

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? ... 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? ... The original problem statement makes not statement about the ... 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)
Quantcast