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)?
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
