#include <stdio.h>
#include <string.h>
//1Gb = 4294967296 bytes available
char number[1<<32];
int main(){
unsigned int x,i;
memset(number,0, sizeof(number));
while( scanf("%ud",&x) > 0){
number[x]=1;
}
for(i=0;;i++)
if(number[i]==0) break;
printf("%d\n",i);
}
Divide in 64 range e run this algorithm
// constructing bitsets
#include <iostream>
#include <string>
#include <bitset>
using namespace std;
//10Mb version = 83 886 080 bits available
#define TENMEGA 10*(1<<20)*8
bitset<TENMEGA> mybits;
string mystring;
int main ()
{
cout << TENMEGA << endl;
size_t x,i;
while( cin >> x ){
if(x < TENMEGA ){
mybits.set(x);
}
}
mystring=mybits.to_string<char,char_traits<char>,allocator<char> >();
cout << "mystring: " << mystring << endl;
for (size_t i=0; i<mybits.size(); ++i)
if ( mybits.test(i)==false ){
cout << i;
break;
}
return 0;
}
Wladimir Araujo Tavares
*Federal University of Ceará
*
On Fri, Mar 18, 2011 at 11:18 AM, ankit sambyal <[email protected]>wrote:
> Assuming each integer takes 4 bytes, for 4 billion numbers it turns out to
> be 16 GB memory required. But we have only 1 GB memory.
> 1. So, break the 16GB file into 16 1GB files.
> 2. Then one by one take each file into memory and run quick sort algorithm
> on it and put it back in the same file. After this step we will be having 16
> 1GB files which are all sorted.
> 3. Then open all the 16 files with 16 file pointers. Read 1 number from
> each file and put it in an array in the memory.
> 4. Then run Min Heapify algorithm on it. Now we will have the smallest
> number at index 0 of the array.
> 5. Remove that number from the array and read a new number into the array
> from the file of which the previous element was deleted.Again run Min
> Heapify algorithm on the array.
> keep on doing this till we find the missing number. Because the number
> deleted in one cycle should be 1 greater than the number deleted in the
> previous cycle. If this condition is not satisfied, we can tell the missing
> number.
>
>
> The algorithm remains same if we have 10 MB memory, only change is that we
> divide the initial file into small files each of size 10 MB.
>
> Thanks and regards,
> Ankit
>
> On Wed, Mar 16, 2011 at 2:18 PM, bittu <[email protected]> wrote:
>
>> Given an input file with four billion integers, provide an algorithm
>> to generate an integer which is not contained in the file. Assume you
>> have 1 GB of memory.
>>
>> 2nd Part
>> What if you have only 10 MB of memory?
>>
>> Thank
>> Shashank
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
