Given 1 GB memory, input a file which contians 4 billion integers, output one integer that is not in the file. What if you have only 10 MB memory?
how to go about this problem???
any efficient algorithms...
ayan2587 -2 Junior Poster in Training
Salem 5,199 Posting Sage
How about you explain what YOU think the answer is, and wait for us to comment on it.
As opposed to merely dumping the assignment on us and waiting for the answer on a plate.
ayan2587 -2 Junior Poster in Training
Given 1 GB memory, input a file which contians 4 billion integers, output one integer that is not in the file. What if you have only 10 MB memory?
how to go about this problem???
any efficient algorithms
I tried to do it in O(N) w/o using any additional memory, checking in O(1) if that number has been seen already.
bool func(int * a, int N)
{
bool var = false;
for (int i = 0; i < N; i++) {
int index = a[i] % N;
if (a[index] > N) {
var = true;
break;
}
a[index] += N;
}
//restore the array
for (int j = 0; j < i; j++)
if (a[j] > N) a[j]
return var;
}i was wondering if there are any other approaches to these kind of problems...thats y put this over here..
also i am unable to get an answer to the second part of the question..so any help wud be appreciated....
How about you explain what YOU think the answer is, and wait for us to comment on it.
As opposed to merely dumping the assignment on us and waiting for the answer on a plate.
Rashakil Fol 978 Super Senior Demiposter Team Colleague
Just output '1' and then copy the contents of the file but don't include any spaces -- the integer you output will be the concatenation of the integers in the input and can't equal any of them.
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.