RE: Searching missing number in large data.

From: "Bobak, Mark" <Mark.Bobak@xxxxxxxxxxxx>
To: "abhishek.gurung@xxxxxxxxxxx" <abhishek.gurung@xxxxxxxxxxx>, Oracle Freelist <oracle-l@xxxxxxxxxxxxx>
Date: Tue, 18 May 2010 08:09:06 -0400

I'd be quite surprised if you find an algorithm that does it less than O(n).

Consider that you have a file with numbers in it.  How can you possibly 
determine which numbers are missing without reading *all* the numbers that are 
present?  There are n numbers, therefore, this would seem to be bound by an 
O(n) algorithm.  Unless I'm missing something subtle?  (Or not so subtle?)

-Mark

From: oracle-l-bounce@xxxxxxxxxxxxx [mailto:oracle-l-bounce@xxxxxxxxxxxxx] On 
Behalf Of Abhishek Gurung
Sent: Tuesday, May 18, 2010 5:20 AM
To: Oracle Freelist
Subject: Searching missing number in large data.

Hi

Problem:
1. There is a file containing numbers form 0 to 2^32 (2 raise to power 32).
2. About 1000 number missing in this range
3. An algo with complexity of log n to find the missing number.


Regards
Abhishek
________________________________
The latest auto launches and test drives Drag n' drop<http://autos.in.msn.com/>

Follow-Ups:

Re: Searching missing number in large data.
From: Adam Musch

References:
- Searching missing number in large data.
  - From: Abhishek Gurung

RE: Searching missing number in large data.

Other related posts: