Are you guys oblivious to the existence of a hashmap data structure?
On Nov 26, 2007 12:15 AM, MJ <[EMAIL PROTECTED]> wrote:
>
> Hi
> I got the answer. Correcting the program as we need to add a condition
> to take care of -ve values
>
> Please correct me if I am wrong
>
> int i = 0;
> int nPair
> while (i<n)
> {
> nPair = X - array[i];
> if(nPair <= 0)
> continue;
> else if(bitmap[nPair] == marked)
> printf("found the answer!");
> else
> bitmap[array[i]] = marked;
> i++;
> }
>
> Thank You,
> Mayur
>
>
>
> On Nov 23, 3:25 pm, MJ <[EMAIL PROTECTED]> wrote:
> > 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 -- 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
-~----------~----~----~----~------~----~------~--~---
