Re: Searching missing number in large data.
- From: Adam Musch <ahmusch@xxxxxxxxx>
- To: Mark.Bobak@xxxxxxxxxxxx
- Date: Tue, 18 May 2010 09:07:46 -0500
Assuming that:
Each number appears once and only once, and;
The numbers are sorted, then one could:
Find value x sub m, beginning at the first record
Find value x sub m+n for some value n
If value x sub m+n - value x sub m = n, then there are no missing
records in the range.
If value x sub m+n - value x sub m != n, then there are missing
records in the range.
Repeat. One would have to check (value x sum m+n) + 1 = (value x sum
m+n+1) as well, checking that there's not a gab between ranges being
checked.
It may be more efficient, but probably not on the order of O(log n).
On Tue, May 18, 2010 at 7:09 AM, Bobak, Mark <Mark.Bobak@xxxxxxxxxxxx> wrote:
> 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
--
Adam Musch
ahmusch@xxxxxxxxx
--
//www.freelists.org/webpage/oracle-l
Other related posts:
