Using segment tree: it does using O(logn) complexity
just check it out:
http://codepad.org/5jVxLmsA
On Sat, Jun 12, 2010 at 2:10 AM, Modeling Expert
cs.modelingexp...@gmail.com wrote:
My previous post went unfinished :((
anyway this is summary of algo . (as N is very large , sorting could
be
As problem says N is very large, I think sorting is not the right
thing as that would be minimum (n log n) time
how about this
Let's say sum is S
we take an mapint,boo map and start reading integerts num
if ( num S ) discard
else {
if ( map[num] == false){
map[ S - num ] = true ;
}
@Expert,
u r right, it will take nlogn time.
But I didn't get this part of the code:
else {
if ( map[num] == false){
map[ S - num ] = true ;
} else {
}
can u please provide us a little explanation?
On Sat, Jun 12, 2010 at 2:34 PM, Modeling Expert
cs.modelingexp...@gmail.com wrote:
My previous post went unfinished :((
anyway this is summary of algo . (as N is very large , sorting could
be costly so this method doesn't do that )
algo ::
have a mapint,bool
1. For given number , if its less than Sum S , make map[S-number] =
true only if map[number] does not exist
2. for Next
