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