Re: searching for missing element in an array

On May 29, 4:45 pm, CBFalconer <cbfalco...@xxxxxxxxx> wrote:
user923005 wrote:
rossum <rossu...@xxxxxxxxxxxx> wrote:
srk <kuma...@xxxxxxxxx> wrote:

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.

Total all the numbers in the array.

The numbers from 1 to n add up to (n * (n + 1)) / 2.

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

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