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 about 512MB of memory. However, if
this operation is in server side and is the bottle neck , the bitmap method
can be tried.
If the integer in the array have a stricted range, like [-x,y], the bitmap
method can be better applied.
Best Regards,
James Fang
-----邮件原件-----
发件人: algogeeks@googlegroups.com [mailto:[EMAIL PROTECTED] 代表
Dave
发送时间: 2007年11月21日 星期三 2:29
收件人: Algorithm Geeks
主题: [algogeeks] Re: Array of integers
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 exhausted array, you deduce
that there is no solution.
You might also want to talk about the size of bitmap.
Dave
On Nov 20, 11:03 am, James Fang <[EMAIL PROTECTED]> wrote:
> 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, with each bit
> represents an integar number.
>
> Best Regards,
> James Fang
>
> On 11月18日, 上午4时42分, geekko <[EMAIL PROTECTED]> wrote:
>
>
>
> > Suppose that you have an array of integers. Given a number X are there
> > any two numbers in the array in which their summation is equal to the
> > X? Can you find a solution in O(n)?- Hide quoted text -
>
> - Show quoted text -
--~--~---------~--~----~------------~-------~--~----~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
