0

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...

3
Contributors
3
Replies
4
Views
7 Years
Discussion Span
Last Post by Rashakil Fol
1

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.

0

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.

0

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.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.