Well if some preprocessing may be done just store the largest number
and increase it.
If the number has to be somewhere in between the 1000000 numbers I
would do it in this way:
Define a Range class: Range{int min, int max}
In the preprocessing split the numbers to free Ranges.
Define Heap<Range> Where Range1>Range2 when (Range1.max-
Range1.min)>(Range2.max-Range2.min).
When you need a new number - take the Range from the top and split it
- O(lgN)
Then add 2 new Ranges to the Heap - O(lgN)
On Feb 20, 11:52 am, "shekhar deo" <[EMAIL PROTECTED]> wrote:
> Please let me know the best solution for this problem :
>
>
>
> > I have a computer file containing 1,000,000 non-negative integers, in
> > no particular order. Imagine that they are the membership numbers of
> > people who are enrolled in my internet club. A new person wants to join
> > the club, and we need to find an unused number to allocate to them. How
> > would you find, in a reasonable time, a number that was not already in the
> > file?
>
> > -
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
