Re: searching for missing element in an array
- From: Ico <usenet@xxxxxxx>
- Date: 29 May 2008 11:48:42 GMT
SRK <kumarsr@xxxxxxxxx> wrote:
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.
Enough sorting algorithms are possible in O(nlogn) time. But you are
probably not allowed to sort, are you ?
The anwer to your assignment is just a trick, no sorting is needed. Try
thinking the other way around: is there something you can say about the
set of numbers [1..n] that you can use to tell if one of those numbers
was missing. For example, can you tell in advance what the sum of all
numbers [1..n] is, without actually adding them all up ?
--
:wq
^X^Cy^K^X^C^C^C^C
.
- Follow-Ups:
- Re: searching for missing element in an array
- From: Juha Nieminen
- Re: searching for missing element in an array
- References:
- Prev by Date: Re: searching for missing element in an array
- Next by Date: Re: searching for missing element in an array
- Previous by thread: Re: searching for missing element in an array
- Next by thread: Re: searching for missing element in an array
- Index(es):
Relevant Pages
|
