Re: Searching missing number in large data.
- From: Adam Musch <ahmusch@xxxxxxxxx>
- To: abhishek.gurung@xxxxxxxxxxx
- Date: Wed, 19 May 2010 09:21:21 -0500
This is not a solvable problem, at least not of less than O(n) complexity.
With an unsorted data set, you won't know if any single number is
missing until having read 2^32 - 1000 - 999 numbers, and you'll only
ever be able to positively identify a missing number after having read
all 2^32 - 1000 of them, because before that point, each number that
hasn't been read is simply more *probably* missing, not *proven*
missing.
If you need O(log n) complexity, you need sorted data.
On Wed, May 19, 2010 at 7:50 AM, Abhishek Gurung
<abhishek.gurung@xxxxxxxxxxx> wrote:
> Hi everyone,
>
> Thanks for looking into this problem.
> I Want to clarify few things.
>
> 1. The numbers are not ordered they are random.
> 2. We have to just find only one of the missing number not all.
> 3. The complexity should be of O(logn) [Big O notation].
>
> Note: I don't know whether the solution exist or not I am looking for it all
> over the net but couldn't got the answer.
>
>
> ________________________________
> The latest auto launches and test drives Drag n' drop
--
Adam Musch
ahmusch@xxxxxxxxx
--
//www.freelists.org/webpage/oracle-l
Other related posts:
