Hi James
On Nov 26, 3:52 pm, "James Fang" <[EMAIL PROTECTED]> wrote:
> The negative "pair value" can be workarounded by normalizing the
> pair to be in the [0,MAX_INT] range.
> This can be achieved by adding MAX_INT/2 to the pair before
> addressing the one bit in the bit map.
I don't think normalization works. Using some small numbers with
MaxInt 127 (8 bit) Array say: 1, -127,... X = -126. -126 - 1 + 63 =
-64, continue, -126 + 127 + 63 = 64 but 1 + 63 not in bitmap. Similar
for 32 bit.
Maybe the question is whether a valid Sum can wrap past MaxInt. If yes
then your original solution is fine otherwise you could add a function
that does the subtraction and returns False if a wrap occures:
class IntSet
new IntSet;
operator in (x: Int32)-> Boolean;
Include(i: Int32);
DeleteVals(Vals: array of Int32; LastIx: Integer);
end IntSet
CheckSub(x, y, *Result: Int32)-> Boolean
Result <- x-y;
return not((a<0)and(b>0)and(Result>0));
end
new NSet: IntSet;
CheckSum(A: array of Int32, X: Int32)-> Boolean
Pair:Int32;
for (i = 0) to (i=A.High)
if (CheckSub(X, A[i], Pair) and (Pair in NSet))
NSet.DeleteVals(A, i);
return true;
else
NSet.Include(A[i]);
end
end
NSet.DeleteVals(A, A.High);
return false;
end
If we are only dealing with positive integers unsigned could be used,
then it makes even less sense to allow wrapping past zero.
As to how IntSet is implemented, bitmap, sparse-array, hash-table,
etc. as Dave said one problem with bitmap is the amount of time to
zero all that memory. A way arround this is to allow only one thread
access to the IntSet, initialize it on start-up and clear only the
bits used by CheckNum, as in the listing, but its size becomes even
more worrying. Think your solution faster than sorting even if hash
table is used, only one operation rather than two, hash table can be
much smaller memory wise. For a time critical application table could
be initialized and maintained as for the bitmap.
Congrats,
- Martin
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
