http://groups.google.com/group/algogeeks - Click on message - View Profile
- Report Profile - Report as Spam
Everyone on this group should do this..
On Nov 19, 2007 8:47 PM, Venkatraman S [EMAIL PROTECTED] wrote:
cant this user be blocked?
On Nov 19, 2007 8:11 PM, Riaz Muhammad [EMAIL
You can acheive O(n) by using a bitmap.
the pseudo code can be described below:
for i=0 to N
pair = X - array[i];
if( bitmap[pair] == marked )
found the answer!
else
mark bitmap[pair]
the bitmap can be an array in the RAM or external disk,
Want to try again?
Consider the case where array = {2,3} and X = 5.
First you have pair = 5 - 2 = 3 and note that bitmap[3] != marked, so
you mark bitmap[3].
Then you have pair = 5 - 3 = 2 and noet that bitmap[2] != marked, so
you mark bitmap[2].
Presumably, at this point, since you have
Oh sorry I've made a mistake in the pseudo code:
It should be rectified like this:
for i=0 to N
pair = X - array[i];
if( bitmap[pair] == marked )
found the answer!
else
mark bitmap[array[i]]
For a 32bit processor , the bitmap takes