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/>
Other related posts:
