I have written a module in Mathematica that searches all possible integer pairs from a specified integer list (which can be negative, null or positive) and that corresponds to an integer specified m.

The only limiting assumption of this algorithm is that the user only wants to get the set of all the unique sums that total m.

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

```
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 are equal
to the smallest and largest entries in the list of integer entries, respectively. *)
(* Let this list be named numberline. *)
(* ::::: Building Number Line BEGINS :::: *)
(* If the listOfIntegers contains only negative integers and possibly zero, *)
Yes[(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, if two or more zeros appear in listOfIntegers, they must be returned to the user.
Therefore, we write m> 0 instead of m [GreaterEqual]0 in the condition above. *)
(* Otherwise, treat it as if all the integers were positive with some considerations. *)
negativeFactor = -1;
sortlist = Invert[-sortedList];
Yes[sortedList[[1]]! = 0,
numberLine = Range[listetriée[SortedList[listetriée[sortedList[[Length[sortedList]]]],
numberLine = Join[{0}beach[listetriée[{0}Range[SortedList[{0}plage[listetriée[{0}Range[sortedList[[Length[sortedList]]]]]]],
negative factor = 1;
(* Else if the whole game contains negative and positive integers, *)
Yes[(sortedList[[1]]<0)&&(sortedList[[Length[sortedList]]]>0)
numberLine =
Join[
-Interval[Abs[Abs[Abdos[Abs[sortedList[[1]]], 0, -1](* negative integer subset *)
,
Interval[listetriée[SortedList[listetriée[sortedList[[Length[sortedList]]]](* positive integer subset *)
], (* Else if the whole game contains only integers, *)
Yes[(sortedList[[1]]== 0) && (sortedList[[Length[sortedList]]]> 0),
(* If the list of integers are all positive and m is negative,
there is no reason to continue. *)
Yes[m <0, execute = False, (* Else, *)
numberLine =
Join[
{0} (* zero *)
,
Interval[listetriée[SortedList[listetriée[sortedList[[Length[sortedList]]]](* whole numbers positive *)
]], (* Else if the entire game contains only natural numbers. *)
(* If the list of integers are all positive and m is negative or zero,
there is no reason to continue. *)
Yes[m<=0,execute=False,numberLine=Range[Max[sortedList](* positive whole numbers *)]]]]];
(* ::::: Numberline construction ENDS :::: *)
(*Impression[numberLine]; *)
Yes[execute==False,finalList=$Failed,
(*Mark all numbers which are in numberline but are not in listOfIntegers with a period.
Sort[] always sort this mixed precision list of numbers in ascending order. *)
temp = Sort[Join[Complement[numberLine,sortedList]// N, sorted list]];
(* The main idea of the algorithm is to find the point on the number line to start selecting two numbers.
combinations that total m. It is obvious that m will be used when that moment comes.
Once this point is selected, integers symmetrically also distant from each other
on both sides of this point (number) in the number line are candidates whose sum is equal to m.
To avoid going outside the limits of the number line (trying to select a lower value)
as the minimum value of numberline or try to select a value greater than the maximum value
value of numberline, here is the maximum distance we can use to get ALL
two whole combinations that total m but also prevent us from going out of bounds.)
*)
(* If the digital line we are about to create has a minimum consistent value of 1
then it would not be compensated as is the case in general.
The following takes into account this "offset". *)
distanceFrom1ToMin = Abs[1-Min[sortedList]];
distance =
Low[
{
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 linked distance established, we are ready to start selecting numbers in Numberline. *)
finalList = {};
i = 1;
While[i<=distance,
finalList=Append[finalList,{temp[[start-i]]temp[[finish+i]]}];
i ++
];
(* It turns out that even for m, the first combination of integers selected is {m / 2, m / 2}. *)
Yes[(Mod[m,2]== 0) && (MemberQ[finalList,{negativeFactor*m/2,negativeFactor*m/2}]== True),
(* There are not two m / 2 in listOfIntegers, we omit this selected combination. *)
Yes[Length[Flatten[Position[listOfIntegers,negativeFactor*m/2]]]<2
finalList = Delete[finalListPosition[finalListPosition[finalListPosition[finalListPosition[finalList,{negativeFactor*m/2,negativeFactor*m/2}][[1]][[1]]]]];
(* We have selected all the possible number combinations in numberline, except if listOfIntegers
is all consecutive integers, we must omit any selected combination of numbers in which either
numbers have a "." to the right of it. *)
finalList = negativeFactor * Sort[Select[finalList,Precision[#]== [Infinity]&]]];
final list
]
```

I did the following tests with the code and got those results. (The first number in the time in seconds that it took to do the math.But you can of course copy the code and do tests yourself.) I have omitted most of the last results test because it made my post too big, but you'll see that he did the math in **0.209207 seconds**.

As the comments of my algorithm (and the algorithm itself suggests), I have divided the numerical line into negative integers, zero and positive integers. I have written my tests to address all possible situations.

**For the whole positive set (not zero).**

*With m such that m is greater than any combination of two numbers of listOfIntegers could possibly give.*

```
m = 100; listOfIntegers = RandomSample[Range[20], 6]AbsoluteTiming[FindTwoIntegersWhoseSumIsM[listOfIntegers, m]]Clear[m, listOfIntegers]
{19, 11, 1, 4, 13, 17}
{0.0371008, {}}
```

*With odd positive 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 m same.*

```
m = 22; listOfIntegers = Beach[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 same m such as listOfIntegers contains two of m / 2.*

```
m = 22; listOfIntegers = Add[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 same m such as listOfIntegers contains an m / 2.*

```
m = 22; listOfIntegers = Beach[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 all negative m.*

```
m = -6; listOfIntegers = Beach[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 all positive integers (including 0).**

*With a same 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 a strange 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 (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 an odd negative m.*

```
m = -17; listOfIntegers =
Random sample[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 =
Random sample[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 whole set negative (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 an odd negative 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 game.**

*With an odd positive m.*

```
m = 15; listOfIntegers =
Random sample[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 an odd negative m.*

```
m = -7; listOfIntegers =
Random sample[Join[Join[Joindre[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 m same.*

```
m = 36; listOfIntegers =
Random sample[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 =
Random sample[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 =
Random sample[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 big m with a big listOfIntegers.*

```
m = 5311; listOfIntegers =
Random sample[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}}}
```