Styjun

I wrote a module in Mathematica which finds all possible pairs of integers from a specified list of integers (which can be negative, zero, or positive) which sum to a specified integer m.

The only limiting assumption this algorithm has is that the user only wishes to get the set of all unique sums which sum to m.

Is there a faster algorithm to do this? I've read that making a Hash table is of complexity O(n). Is my code of time O(n)? If it of time O(n), is it a Hash table, or is it something else? If it is not of time O(n), how efficient is it?

FindTwoIntegersWhoseSumIsM[listOfIntegers_,m_]:=Module[

i,distanceFrom1ToMin,negativeFactor,distance,start,finish,(*Integers*)
sortedList,numberLine,temp,finalList,(*Lists*)
execute(*Boolean*)
,
(*There are possible inputted values of m with a give integer set input which
make the execution of this algorithm unnecessary.*)
execute=True;

sortedList=Sort[DeleteDuplicates[listOfIntegers]];

(*Create a continuous list of integers whose smallest and largest entries is equal
to the smallest and largest entries of the inputted list of integers, respectively.*)
(*Let this list be named numberline.*)

(*:::::Construction of numberline BEGINS::::*)

(*If the listOfIntegers only contains negative integers and possibly zero,*)
If[(sortedList[[1]]<0)&&(sortedList[[Length[sortedList]]]<=0),

 (*If m is positive, there is no reason to proceed.*)

 If[m>0,execute=False,
 (*If m [Equal] 0 then if two or more zeros are in listOfIntegers, they should be outputted to the user.
 Therefore, we write m>0 instead of m[GreaterEqual]0 in the conditional above.*)

 (*Otherwise, treat it as if all integers were positive with a few considerations.*)
 negativeFactor=-1;
 sortedList=Reverse[-sortedList];
 If[sortedList[[1]]!=0,
 numberLine=Range[sortedList[[Length[sortedList]]]]
 ,
 numberLine=Join[0,Range[sortedList[[Length[sortedList]]]]]
 ]
 ]
,
negativeFactor=1;

(*Else If the integer set contains negative and positive integers,*)
 If[(sortedList[[1]]<0)&&(sortedList[[Length[sortedList]]]>0),
 numberLine=
 Join[
 -Range[Abs[sortedList[[1]]],0,-1](*negative integer subset*)
 ,
 Range[sortedList[[Length[sortedList]]]](*positive integer subset*)
 ]
,(*Else if the integer set contains only whole numbers,*)
 If[(sortedList[[1]]==0)&&(sortedList[[Length[sortedList]]]>0),

 (*If the list of integers are all positive and m is negative,
 there is no reason to proceed.*)
 If[m<0,execute=False,(*Otherwise,*)
 numberLine=
 Join[
 0(*zero*)
 ,
 Range[sortedList[[Length[sortedList]]]](*positive integers*)
 ]
 ]
,(*Else if the integer set contains only the natural numbers.*)

 (*If the list of integers are all positive and m is negative or zero,
 there is no reason to proceed.*)
 If[m<=0,execute=False,numberLine=Range[Max[sortedList](*positive integers*)]]
 ]
 ]
];

(*:::::Construction of numberline ENDS::::*)
(*Print[numberLine];*)


If[execute==False,finalList=$Failed,
(*Mark all numbers which are in numberline but are not in listOfIntegers with a period.

Sort[] will still sort this list of mixed precision of numbers in ascending order.*)
temp=Sort[Join[Complement[numberLine,sortedList]//N,sortedList]];

(*The main idea of the algorithm is to find the point on numberline to begin selecting two number
combinations which sum to m. m is obviously going to be used when that time comes.

Once that point is selected, integers symmetrically equally distant apart from each other
on both sides of this point (number) in numberline are candidates which sum to m.

To avoid going "out of bounds" of numberline (from either attempting to select a value smaller
than the minimum value of numberline or attempting to select a larger value than the maximum
value of numberline, the following is the maximum distance we can use to obtain ALL possible
two integer combinations which sum to m but of which also prevents us from going "out of bounds".)
*)


(*If the numberline we are about to create had a consistent minimum value of 1
then it would not be offset as it is in general.
The following takes this "offset" into account.*)
distanceFrom1ToMin=Abs[1-Min[sortedList]];


distance=
Min[
 
 distanceFrom1ToMin+Floor[negativeFactor*m/2]
 ,
 Length[temp]-(distanceFrom1ToMin+Ceiling[negativeFactor*m/2]-1)
 
];

start=distanceFrom1ToMin+Floor[negativeFactor*m/2]+1;
finish=distanceFrom1ToMin+Ceiling[negativeFactor*m/2]-1;

(*With the bound distance established, we are ready to begin selecting numbers from numberline.*)
finalList=;
i=1;
While[i<=distance,
 finalList=Append[finalList,temp[[start-i]],temp[[finish+i]]];
 i++
];

(*It turns out that for even m the first selected integer combination considered is m/2,m/2.*)
If[(Mod[m,2]==0)&&(MemberQ[finalList,negativeFactor*m/2,negativeFactor*m/2]==True),
(*Should there not be two of m/2 in listOfIntegers, we omit this selected combination.*)
 If[Length[Flatten[Position[listOfIntegers,negativeFactor*m/2]]]<2,
 finalList=Delete[finalList,Position[finalList,negativeFactor*m/2,negativeFactor*m/2][[1]][[1]]]
 ]
];

(*We selected all possible number combinations in numberline. However, unless listOfIntegers
is all consecutive integers, we need to omit any selected number combination in which either
of the numbers has a "." to the right of it.*)
finalList=negativeFactor*Sort[Select[finalList,Precision[#]==[Infinity]&]]
];
finalList
]

I did the following tests with the code and got these results. (The first number in the time in second it took to do the computation. But you can of course copy the code and do tests yourself.) I omitted most of the results from the last test because it made my post too large, but you will see that it did the computation in 0.209207 seconds.

As the comments in my algorithm (and the algorithm itself suggests), I broke up the number line into negative integers, zero, and the positive integers. I therefore wrote my tests to address all possible situations.

For the positive (non-zero) integer set.

With positive m such that m is larger than what any two number combination in listOfIntegers could possibly sum to.

m = 100; listOfIntegers = RandomSample[Range[20], 6]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]

19, 11, 1, 4, 13, 17

0.0371008, 

With positive odd m.

m = 215; listOfIntegers = RandomSample[Range[266], 190]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]

119, 175, 7, 123, 42, 173, 15, 56, 233, 41, 9, 156, 130, 196, 183, 
65, 102, 109, 177, 161, 230, 105, 91, 103, 146, 47, 234, 133, 88, 68, 
169, 197, 46, 198, 108, 263, 205, 129, 4, 157, 245, 210, 203, 78, 
172, 128, 138, 61, 262, 159, 148, 45, 225, 239, 72, 74, 151, 34, 36, 
5, 106, 77, 223, 116, 8, 2, 11, 54, 124, 87, 221, 213, 171, 93, 53, 
19, 40, 30, 95, 215, 39, 140, 49, 158, 94, 38, 28, 247, 84, 75, 257, 
33, 163, 132, 69, 211, 193, 222, 114, 240, 32, 149, 167, 135, 107, 
115, 101, 100, 166, 144, 251, 253, 224, 154, 48, 44, 26, 181, 259, 
81, 6, 70, 122, 255, 189, 235, 112, 110, 174, 85, 147, 117, 18, 209, 
66, 121, 155, 206, 207, 212, 98, 113, 254, 214, 178, 111, 227, 165, 
204, 231, 194, 20, 176, 150, 162, 241, 243, 199, 90, 55, 127, 191, 
12, 185, 242, 125, 265, 25, 1, 250, 201, 168, 76, 134, 266, 82, 10, 
92, 143, 217, 126, 218, 182, 220, 153, 164, 216, 238, 67, 14

0.136695, 1, 214, 2, 213, 4, 211, 5, 210, 6, 209, 8, 
 207, 9, 206, 10, 205, 11, 204, 12, 203, 14, 201, 18, 
 197, 19, 196, 26, 189, 30, 185, 32, 183, 33, 182, 34, 
 181, 38, 177, 39, 176, 40, 175, 41, 174, 42, 173, 44, 
 171, 46, 169, 47, 168, 48, 167, 49, 166, 53, 162, 54, 
 161, 56, 159, 61, 154, 65, 150, 66, 149, 67, 148, 68, 
 147, 69, 146, 72, 143, 75, 140, 77, 138, 81, 134, 82, 
 133, 85, 130, 87, 128, 88, 127, 90, 125, 91, 124, 92, 
 123, 93, 122, 94, 121, 98, 117, 100, 115, 101, 
 114, 102, 113, 103, 112, 105, 110, 106, 109, 107, 108

With positive even m.

m = 22; listOfIntegers = Range[20]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

0.00998522, 2, 20, 3, 19, 4, 18, 5, 17, 6, 16, 7, 
 15, 8, 14, 9, 13, 10, 12

With positive even m such that listOfIntegers contains two of m/2.

m = 22; listOfIntegers = Append[Range[20], 11]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 
20, 11

0.00037181, 2, 20, 3, 19, 4, 18, 5, 17, 6, 16, 7, 
 15, 8, 14, 9, 13, 10, 12, 11, 11

With positive even m such that listOfIntegers contains one m/2.

m = 22; listOfIntegers = Range[20]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

0.000267311, 2, 20, 3, 19, 4, 18, 5, 17, 6, 16, 7, 
 15, 8, 14, 9, 13, 10, 12

With any negative m.

m = -6; listOfIntegers = Range[26]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 
20, 21, 22, 23, 24, 25, 26

0.000108231, $Failed

For the positive integer set (including 0).

With an even m.

m = 88; listOfIntegers = RandomSample[Join[0, Range[122]], 39]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]

121, 69, 120, 56, 36, 55, 17, 114, 7, 59, 32, 4, 20, 79, 92, 62, 50, 
89, 13, 70, 113, 75, 76, 80, 108, 53, 83, 95, 0, 85, 86, 77, 10, 54, 
48, 66, 104, 100, 35

0.000505232, 13, 75, 32, 56, 35, 53

With an odd m.

m = 57; listOfIntegers = RandomSample[Join[0, Range[82]], 52]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]

62, 18, 26, 0, 67, 34, 55, 52, 35, 78, 10, 68, 46, 44, 38, 23, 77, 
76, 58, 51, 75, 63, 53, 42, 54, 27, 56, 71, 12, 17, 2, 37, 31, 72, 
49, 50, 32, 16, 47, 19, 4, 20, 81, 25, 61, 14, 80, 82, 59, 33, 70, 39

0.000372743, 2, 55, 4, 53, 10, 47, 18, 39, 19, 38, 20, 
 37, 23, 34, 25, 32, 26, 31

For the negative integer set (including 0).

With a positive m.

m = 4; listOfIntegers = RandomSample[Join[0, -Range[22, 1, -1]], 19]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]

-2, -16, -15, -9, -5, -12, -8, -22, -7, -21, -13, -18, -4, -11, -10, 
-19, -6, -17, -20

0.000105898, $Failed

With a negative odd m.

m = -17; listOfIntegers = 
 RandomSample[Join[0, -Range[22, 1, -1]], 19]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]

-5, -1, -10, -13, -15, -19, -2, 0, -7, -18, -3, -21, -8, -11, -12, 
-22, -17, -16, -20

0.000640987, 0, -17, -1, -16, -2, -15, -5, -12, -7, -10

With a negative even m.

m = -26; listOfIntegers = 
 RandomSample[Join[0, -Range[22, 1, -1]], 19]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]

-19, -16, -11, -14, -17, -13, -1, -9, -15, -20, -18, -4, -21, 0, -8, 
-6, -10, -7, -3

0.000329357, -6, -20, -7, -19, -8, -18, -9, -17, -10, 
-16, -11, -15

For the negative integer set (excluding 0).

With a positive m.

m = 4; listOfIntegers = RandomSample[-Range[22, 1, -1], 19]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]

-20, -7, -16, -21, -11, -13, -5, -2, -6, -19, -1, -12, -18, -14, 
-15, -9, -4, -17, -22

0.000102633, $Failed

With a negative odd m.

m = -27; listOfIntegers = RandomSample[-Range[22, 1, -1], 19]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]

-18, -17, -22, -13, -1, -11, -19, -8, -16, -6, -21, -12, -20, -3, 
-4, -9, -7, -14, -15

0.000242586, -6, -21, -7, -20, -8, -19, -9, -18, -11, 
-16, -12, -15, -13, -14

With a negative even m.

m = -26; listOfIntegers = RandomSample[-Range[22, 1, -1], 19]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]

-19, -10, -20, -9, -21, -14, -5, -1, -17, -4, -18, -22, -8, -6, -13, 
-3, -2, -12, -15

0.000286438, -4, -22, -5, -21, -6, -20, -8, -18, -9, -17, 
-12, -14

For the complete integer set.

With a positive odd m.

m = 15; listOfIntegers = 
 RandomSample[Join[-Range[52, 1, -1], 0, Range[52]], 35]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]

-30, 19, 42, 38, -25, 6, 48, 5, -8, -27, -11, -47, -37, -12, -3, 
-34, 50, 11, 10, 18, 7, -15, 51, -22, -26, -2, 33, -35, 34, 39, 44, 
-51, -33, -16, -23

0.000468378, -35, 50, -33, 48, -27, 42, -23, 38, -3, 
 18, 5, 10

With a negative odd m.

m = -7; listOfIntegers = 
 RandomSample[Join[-Range[22, 1, -1], 0, Range[22]], 21]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]

-1, -16, -11, 10, 17, 1, 0, -5, -22, 8, -7, 15, 21, 11, 18, 14, -4, 
7, -13, 4, -9

0.000310697, -22, 15, -11, 4, -7, 0

With a positive even m.

m = 36; listOfIntegers = 
 RandomSample[Join[-Range[30, 1, -1], 0, Range[30]], 20]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]

25, -9, -8, 8, 5, -10, -24, 13, 9, -16, -23, -14, -22, -29, 26, 12, 
19, 16, -30, 18

0.000289237, 

With a negative even m.

m = -34; listOfIntegers = 
 RandomSample[Join[-Range[100, 1, -1], 0, Range[100]], 50]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]

7, 92, 91, 58, -58, 63, -95, 82, 26, 60, 16, 65, 15, 34, 29, 67, -2, 
88, 21, -72, -93, 12, 43, 18, -83, -80, -30, -6, 54, -13, -63, 39, 
-55, 9, -78, 5, -16, 52, -24, -82, -18, 2, -90, 37, -60, 80, 57, -22, 
-26, 72

0.000726359, -63, 29, -60, 26, -55, 21, -18, -16

With m == 0.

m = 0; listOfIntegers = 
 RandomSample[Join[-Range[222, 1, -1], 0, Range[222]], 111]
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]
Clear[m, listOfIntegers]

-215, -8, 186, 153, 17, 83, 149, -45, -18, 14, -161, 6, 84, -41, 
-59, -130, 34, -24, -142, -95, -70, -60, -152, 90, -43, 12, -196, 
-98, -193, -78, -192, 7, -30, 218, -209, -28, -125, 142, 11, 161, 
-143, -135, -212, 134, 1, -177, -100, 2, 63, -180, -50, 79, -129, 
-91, 126, 57, -140, -200, 38, -182, -107, -25, -46, -179, -113, 88, 
148, 28, 184, -158, 190, -9, -36, -5, 169, 221, -204, -210, 44, 45, 
-71, 40, 135, 119, -42, 166, 65, 59, -15, -118, 117, -47, -52, 102, 
74, -19, 152, 81, 0, 170, -214, 114, -38, 210, -1, -7, -89, -173, 
123, 78, -127

0.00179934, -210, 210, -161, 161, -152, 152, -142, 
 142, -135, 135, -78, 78, -59, 59, -45, 45, -38, 
 38, -28, 28, -7, 7, -1, 1

With a large m with a large listOfIntegers.

m = 5311; listOfIntegers = 
 RandomSample[Join[-Range[9999, 1, -1], 0, Range[9999]], 8888];
AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]

0.209207, -4680, 9991, -4676, 9987, -4664, 9975, -4650, 
 9961, -4646, 9957, -4645, 9956, -4636, 9947, -4634, 
 9945, -4633, 9944, -4630, 9941, -4600, 9911, -4599, 
 9910, -4594, 9905, -4587, 9898, -4574, 9885, -4573, 
 9884, -4572, 9883, -4566, 9877, -4562, 9873, -4556, 
 9867, -4549, 9860, -4538, 9849, -4529, 9840, -4517, 
 9828, -4514, 9825, -4511, 9822, -4504, 9815, -4502, 
 9813, -4499, 9810, -4497, 9808, -4490, 9801, -4486, 
 9797, -4485, 9796, -4483, 9794, -4481, 9792, -4478, 
 9789, -4475, 9786, -4464, 9775, -4463, 9774, -4458, 
 9769, -4452, 9763, -4443, 9754, -4431, 9742, -4428, 
 9739, -4427, 9738, -4420, 9731, -4417, 9728, -4407, 
 9718, -4405, 9716, -4397, 9708, -4394, 9705, -4393, 
 9704, -4380, 9691, -4377, 9688, -4369, 9680, -4359, 
 9670, -4356, 9667, -4354, 9665, -4350, 9661, -4349, 
 9660, -4346, 9657, -4337, 9648, -4332, 9643, -4331, 
 9642, -4325, 9636, -4323, 9634, -4314, 9625, -4305, 
 9616, -4293, 9604, -4283, 9594, -4266, 9577, -4246, 
 9557, -4241, 9552, -4235, 9546, -4231, 9542, -4227, 
 9538, -4224, 9535, -4222, 9533, -4220, 9531, -4211, 
 9522, -4203, 9514, -4202, 9513, -4198, 9509, -4196, 
 9507, -4193, 9504, -4190, 9501, -4181, 9492, -4176, 
 9487, -4148, 9459, -4138, 9449, -4137, 9448, -4136, 
 9447, -4127, 9438, -4125, 9436, -4107, 9418, -4086, 
 9397, -4081, 9392, -4079, 9390, -4078, 9389, -4065, 
 9376, -4056, 9367, -4041, 9352, -4040, 9351, -4038, 
 9349, -4035, 9346, -4030, 9341, -4026, 9337, -4020, 
 9331, -4015, 9326, -4014, 9325, -4010, 9321, -3991, 
 9302, -3988, 9299, -3984, 9295, -3980, 9291, -3978, 
 9289, -3977, 9288, -3976, 9287, -3971, 9282, -3970, 
 9281, -3950, 9261, -3946, 9257, -3938, 9249, -3932, 
 9243, -3922, 9233, -3920, 9231, -3915, 9226, -3910, 
 9221, -3909, 9220, -3908, 9219, -3901, 9212, -3900, 
 9211, -3898, 9209, -3887, 9198, -3885, 9196, -3877, 
 9188, -3875, 9186, -3869, 9180, -3864, 9175, -3859, 
 9170, -3854, 9165, -3853, 9164, -3848, 9159, -3839, 
 9150, -3835, 9146, -3826, 9137, -3821, 9132, -3812, 
 9123, -3810, 9121, -3807, 9118, -3806, 9117, -3799, 
 9110, -3797, 9108, -3789, 9100, -3779, 9090, -3777, 
 9088, -3774, 9085, -3773, 9084, -3769, 9080, -3767, 
 9078, -3761, 9072, -3751, 9062, -3750, 9061, -3749, 
 9060, -3748, 9059, -3742, 9053, -3740, 9051, -3731, 
 9042, -3726, 9037, -3717, 9028, -3715, 9026, -3714, 
 9025, -3708, 9019, -3704, 9015, -3702, 9013, -3687, 
 8998, -3677, 8988, -3661, 8972, -3654, 8965, -3653, 
 8964, -3649, 8960, -3641, 8952, -3635, 8946, -3622, 
 8933, -3615, 8926, -3610, 8921, -3607, 8918, -3601, 
 8912, -3597, 8908, -3592, 8903, -3586, 8897, ... , 2594, 2717, 2598, 2713, 2599, 2712, 2603, 
 2708, 2607, 2704, 2617, 2694, 2619, 2692, 2633, 
 2678, 2634, 2677, 2643, 2668, 2644, 2667, 2648, 
 2663, 2650, 2661

I think

IntegerPartitions[m, 2, listOfIntegers]

does exactly what you want, and seems pretty efficient.

Your algorithm certainly isn't $O(n)$, just because sort has a theoretical lower bound of $O(n log(n))$. I don't know what exactly you're trying to do in your algorithm, but the problem is a classic one. One solving strategy is:

1. Sort the list of numbers


2. For each number $a_i$ in the list, conduct a binary search for the number $a_j= m - a_i$. If there is such a number $a_j$ for $i neq j$, output the tuple $(a_i,a_j)$.

Put together, this algorithm yields a runtime of $O(nlog(n))$, because binary search runs in $O(log(n))$ and you need to do it $n$ times and sorting is $O(nlog(n))$ anyways.