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