I think we might need to be more specific about this problem
1) Are all these number distinct, i.e. if there are duplicate number in
these numbers?
2) Is there only one number missing?
3) do we know the range of these numbers for example n=300million
If yes to question 1)-3) we could try xor method, it only takes some bytes
O(n) time, O(1) space
In general: xor1=xor1^x[0]^...,x[n-1]
then xor1=xor1^1,...,n
then return xor1 (we can read all element from file sequentially)
If no to question 2, we could try this: if we know the range: 1...n, then
sequentially read the number, if it is less than n/2, we output to file A
other wise to file B. We count the size of file A and file B. If file A's
size is less than n/2, then the missing number is in file A. Then we read
number from file A, proceed the above procedure, test with number n/4. The
procedure goes on until we find the missing. The method only works on there
is no duplicate in the numbers.
On Thu, Jun 23, 2011 at 11:17 AM, atul purohit <gonewiththe...@gmail.com>wrote:
> Hi,
>
> While external sorting is a probable way to sort it. Still it changes the
> content and time complexity will be > O(n). It is a trivial job to copy the
> entire file and do the sorting and find a number which is not present in
> file but I am looking for a solution which essentially does the job in O(n).
>
> Thanks.
> Atul
> On Thu, Jun 23, 2011 at 6:59 PM, Douglas Diniz <dgdi...@gmail.com> wrote:
>
>> If the file is sorted, use binary search. Divide the file in blocks of
>> 2MB. Choose the blocks using binary search, an inside the block use
>> binary search again to find the number.
>>
>> If the file isn't sorted, sort the file with cosequential process,
>> then use binary search.
>> To learn cosequential process see the book File Structure from Folk.
>> With cosequential process you can sort a terabyte file with only 100
>> bytes of Ram, for example.
>>
>> Or you can divide the file in blocks of 2MB or less and check all this
>> blocks for the number.
>>
>> On Thu, Jun 23, 2011 at 9:59 AM, atul purohit <gonewiththe...@gmail.com>
>> wrote:
>> >
>> > Hi,
>> > Can someone explain me how to do this.
>> > Given a file containing roughly 300 million 9-digit numbers. Find a
>> 9-digit
>> > number that isn't present in the file.You have unlimited drive space but
>> > only 2MB of RAM available.
>> > I suppose we have to use bit-vectors n all but still couldnt figure out
>> a
>> > proper way. A few steps or an algo will be great.
>> > Cheers,
>> > Atul
>> >
>> > --
>> > 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
>> > algogeeks+unsubscr...@googlegroups.com.
>> > For more options, visit this group at
>> > http://groups.google.com/group/algogeeks?hl=en.
>> >
>>
>>
>>
>> --
>> -------------------------------------------------------------------
>> Douglas Gameiro Diniz
>> Engenheiro de Computação - 2003 - UNICAMP
>>
>> Mobile: (19) 92158777
>> Gtalk: dgdiniz
>> Msn: thedougdi...@hotmail.com
>>
>> --
>> 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
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>
>
> --
>
> Atul Purohit
>
> --
> 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
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
