Hi James,
As per your solution the variable pair can go negative and if Array[i]
> X,
and in that case you can not use bitmap[pair] which will give an
exception as we can not access the array elements using -ve value.
SO how will you take care of -ve values of variable "pair"...
pair = X - array[i]; //this
can go negative
if( bitmap[pair] == marked ) // if pair is -
ve value this operation is not allowed
found the answer!
else
mark bitmap[array[i]]
Thank You,
Mayur
On Nov 23, 2:22 pm, MJ <[EMAIL PROTECTED]> wrote:
> Hi
> James, your approach is cool, The bitmap approach works in O(n),
>
> but as mention by dave, it take extra memory and initialization.
>
> If we dont want to use extra memory, can it be done in O(n)?
>
> Thank You
> MJ
>
> On Nov 21, 8:11 pm, Dave <[EMAIL PROTECTED]> wrote:
>
>
>
> > Okay. This works better. It is O(n), but also requires a large amount
> > of extra memory ( regard 512MB to be large), with a corresponding huge
> > constant overhead to initialize the bitmap. Can you estimate, using
> > reasonable assumptions, the n for which the O(n log n) algorithm using
> > sorting would be faster than this algorithm. I think you will find the
> > breakeven point to be pretty large, perhaps 2^20 or more. So, for n =
> > 10, 100, or 1000, the bitmap as you describe it would be pretty
> > impractical.
>
> > This raises the interesting question: How do you trade off lower
> > asymptotic order with possible higher cost for smaller values of n.
> > There are some places where this tradeoff is crucial to program
> > performance. For example, in manipulating sparse matrices, a common
> > operation is as follows:
>
> > for i = 1 to n
> > y[index[i]] = a * x[i] + y[index[i]];
>
> > You can write code to be fast for large n, but it is more important to
> > be fast for small n because most of the time n will be small.
>
> > Dave
>
> > On Nov 20, 7:30 pm, "James Fang" <[EMAIL PROTECTED]> wrote:
>
> > > 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 -- Hide quoted text -
>
> > > - Show quoted text -- Hide quoted text -
>
> > - Show quoted text -- 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
-~----------~----~----~----~------~----~------~--~---
