Re: searching for missing element in an array

On May 29, 4:06 pm, Ico <use...@xxxxxxx> 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.

Homework ? Then sorting and iterating the array until you find the
missing number is not the answer you're looking for, is it ?

--
:wq
^X^Cy^K^X^C^C^C^C

Definately I am not looking for O(n2) complexity. I want max O(n) or
O(nlogn) complexity.
.

Relevant Pages

  • Re: best method to find the freequent numbers
    ... My array size is huge. ... There two common "types" of complexity: ... For calculating expected complexity you need to know something about the ... I guess the best approach is some kind of sorting and then scanning through ...
    (comp.lang.c)
  • 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)