The most efficient algorithm to find all possible integer pairs which sum to a given integer












3












$begingroup$


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









share|improve this question









New contributor




Christopher Mowla is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$












  • $begingroup$
    The presence of an Append indicates that the complexity of the algorithm is larger than you expect...
    $endgroup$
    – Henrik Schumacher
    Mar 25 at 18:04










  • $begingroup$
    You have a Sort call. Use SortBy instead, it is much faster than Sort. But you probably don't need to sort it anyway.
    $endgroup$
    – MikeY
    Mar 25 at 18:37










  • $begingroup$
    According to my knowledge, I did need to use some type of sort for my algorithm. However, I clearly see now (by Roman's post) that my algorithm isn't the most efficient out there. So I guess I'm not worried about it anymore. I wrote this algorithm as part as my coding challenge for a position at Wolfram Research about four months ago. I was just curious if someone could identify what I did or if it is a new way to approach this old classic problem. Thanks, guys!
    $endgroup$
    – Christopher Mowla
    Mar 25 at 21:58










  • $begingroup$
    Assuming the hashing and lookup are O(1), an O(n) method is as follows. (1) Hash all values in the list. (2) Iterate over the list, checking for each value k whether m-k was hashed. Can use Sow to record the pair, and Reap to gather all pairs sown.
    $endgroup$
    – Daniel Lichtblau
    Mar 27 at 23:15
















3












$begingroup$


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









share|improve this question









New contributor




Christopher Mowla is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$












  • $begingroup$
    The presence of an Append indicates that the complexity of the algorithm is larger than you expect...
    $endgroup$
    – Henrik Schumacher
    Mar 25 at 18:04










  • $begingroup$
    You have a Sort call. Use SortBy instead, it is much faster than Sort. But you probably don't need to sort it anyway.
    $endgroup$
    – MikeY
    Mar 25 at 18:37










  • $begingroup$
    According to my knowledge, I did need to use some type of sort for my algorithm. However, I clearly see now (by Roman's post) that my algorithm isn't the most efficient out there. So I guess I'm not worried about it anymore. I wrote this algorithm as part as my coding challenge for a position at Wolfram Research about four months ago. I was just curious if someone could identify what I did or if it is a new way to approach this old classic problem. Thanks, guys!
    $endgroup$
    – Christopher Mowla
    Mar 25 at 21:58










  • $begingroup$
    Assuming the hashing and lookup are O(1), an O(n) method is as follows. (1) Hash all values in the list. (2) Iterate over the list, checking for each value k whether m-k was hashed. Can use Sow to record the pair, and Reap to gather all pairs sown.
    $endgroup$
    – Daniel Lichtblau
    Mar 27 at 23:15














3












3








3





$begingroup$


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









share|improve this question









New contributor




Christopher Mowla is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$




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






algorithm code-review






share|improve this question









New contributor




Christopher Mowla is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











share|improve this question









New contributor




Christopher Mowla is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









share|improve this question




share|improve this question








edited Mar 25 at 18:04









Henrik Schumacher

58.6k581162




58.6k581162






New contributor




Christopher Mowla is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









asked Mar 25 at 17:45









Christopher MowlaChristopher Mowla

1185




1185




New contributor




Christopher Mowla is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.





New contributor





Christopher Mowla is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






Christopher Mowla is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.












  • $begingroup$
    The presence of an Append indicates that the complexity of the algorithm is larger than you expect...
    $endgroup$
    – Henrik Schumacher
    Mar 25 at 18:04










  • $begingroup$
    You have a Sort call. Use SortBy instead, it is much faster than Sort. But you probably don't need to sort it anyway.
    $endgroup$
    – MikeY
    Mar 25 at 18:37










  • $begingroup$
    According to my knowledge, I did need to use some type of sort for my algorithm. However, I clearly see now (by Roman's post) that my algorithm isn't the most efficient out there. So I guess I'm not worried about it anymore. I wrote this algorithm as part as my coding challenge for a position at Wolfram Research about four months ago. I was just curious if someone could identify what I did or if it is a new way to approach this old classic problem. Thanks, guys!
    $endgroup$
    – Christopher Mowla
    Mar 25 at 21:58










  • $begingroup$
    Assuming the hashing and lookup are O(1), an O(n) method is as follows. (1) Hash all values in the list. (2) Iterate over the list, checking for each value k whether m-k was hashed. Can use Sow to record the pair, and Reap to gather all pairs sown.
    $endgroup$
    – Daniel Lichtblau
    Mar 27 at 23:15


















  • $begingroup$
    The presence of an Append indicates that the complexity of the algorithm is larger than you expect...
    $endgroup$
    – Henrik Schumacher
    Mar 25 at 18:04










  • $begingroup$
    You have a Sort call. Use SortBy instead, it is much faster than Sort. But you probably don't need to sort it anyway.
    $endgroup$
    – MikeY
    Mar 25 at 18:37










  • $begingroup$
    According to my knowledge, I did need to use some type of sort for my algorithm. However, I clearly see now (by Roman's post) that my algorithm isn't the most efficient out there. So I guess I'm not worried about it anymore. I wrote this algorithm as part as my coding challenge for a position at Wolfram Research about four months ago. I was just curious if someone could identify what I did or if it is a new way to approach this old classic problem. Thanks, guys!
    $endgroup$
    – Christopher Mowla
    Mar 25 at 21:58










  • $begingroup$
    Assuming the hashing and lookup are O(1), an O(n) method is as follows. (1) Hash all values in the list. (2) Iterate over the list, checking for each value k whether m-k was hashed. Can use Sow to record the pair, and Reap to gather all pairs sown.
    $endgroup$
    – Daniel Lichtblau
    Mar 27 at 23:15
















$begingroup$
The presence of an Append indicates that the complexity of the algorithm is larger than you expect...
$endgroup$
– Henrik Schumacher
Mar 25 at 18:04




$begingroup$
The presence of an Append indicates that the complexity of the algorithm is larger than you expect...
$endgroup$
– Henrik Schumacher
Mar 25 at 18:04












$begingroup$
You have a Sort call. Use SortBy instead, it is much faster than Sort. But you probably don't need to sort it anyway.
$endgroup$
– MikeY
Mar 25 at 18:37




$begingroup$
You have a Sort call. Use SortBy instead, it is much faster than Sort. But you probably don't need to sort it anyway.
$endgroup$
– MikeY
Mar 25 at 18:37












$begingroup$
According to my knowledge, I did need to use some type of sort for my algorithm. However, I clearly see now (by Roman's post) that my algorithm isn't the most efficient out there. So I guess I'm not worried about it anymore. I wrote this algorithm as part as my coding challenge for a position at Wolfram Research about four months ago. I was just curious if someone could identify what I did or if it is a new way to approach this old classic problem. Thanks, guys!
$endgroup$
– Christopher Mowla
Mar 25 at 21:58




$begingroup$
According to my knowledge, I did need to use some type of sort for my algorithm. However, I clearly see now (by Roman's post) that my algorithm isn't the most efficient out there. So I guess I'm not worried about it anymore. I wrote this algorithm as part as my coding challenge for a position at Wolfram Research about four months ago. I was just curious if someone could identify what I did or if it is a new way to approach this old classic problem. Thanks, guys!
$endgroup$
– Christopher Mowla
Mar 25 at 21:58












$begingroup$
Assuming the hashing and lookup are O(1), an O(n) method is as follows. (1) Hash all values in the list. (2) Iterate over the list, checking for each value k whether m-k was hashed. Can use Sow to record the pair, and Reap to gather all pairs sown.
$endgroup$
– Daniel Lichtblau
Mar 27 at 23:15




$begingroup$
Assuming the hashing and lookup are O(1), an O(n) method is as follows. (1) Hash all values in the list. (2) Iterate over the list, checking for each value k whether m-k was hashed. Can use Sow to record the pair, and Reap to gather all pairs sown.
$endgroup$
– Daniel Lichtblau
Mar 27 at 23:15










2 Answers
2






active

oldest

votes


















16












$begingroup$

I think



IntegerPartitions[m, {2}, listOfIntegers]


does exactly what you want, and seems pretty efficient.






share|improve this answer









$endgroup$













  • $begingroup$
    Thanks! I have used IntegerPartitions for some Rubik's cube theory in the past (cycle types), but I didn't know that it can be used to select partitions from a custom list. I ran it and my algorithm on a larger data set than the largest listed on here, and my algorithm took 31 seconds, whereas IntegerPartitions took 16 seconds. Impressive. I originally wrote my algorithm as part of a coding interview at Wolfram Research, but they didn't hire me for the position. I guess I see why now. LOL.
    $endgroup$
    – Christopher Mowla
    Mar 25 at 21:52






  • 2




    $begingroup$
    @ChristopherMowla - But also, native functions use pre-compiled code, so have an advantage over your solution. See blog.wolfram.com/2011/12/07/…, especially the second point, if you'd like to optimize your code a bit for better comparison.
    $endgroup$
    – Andrew Cheong
    Mar 26 at 5:28





















2












$begingroup$

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.






share|improve this answer








New contributor




Simon Erni is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






$endgroup$









  • 1




    $begingroup$
    You don't need to conduct any binary searches! Just make two simultaneous passes through the sorted list, one in increasing order and one in decreasing order. If the sum of the two scanned elements is less than $m$, increase the lower one; else decrease the higher one. Repeat until they meet in the middle. This is $O(n)$. (Of course the total complexity is still $O(nlog n)$ because of the sorting stage.)
    $endgroup$
    – TonyK
    Mar 26 at 14:21










  • $begingroup$
    @Simon, even though my code may look long, the majority of it is comments explaining the algorithm. If you are interested in knowing what I DID (not what I'm "trying to do") with my algorithm, start reading the comments from the line which states "The main idea of the algorithm is to find the point on numberline to begin selecting two number combinations which sum to m". All lines of code previous to that are for creating the list named numberLine and determining values of some booleans to end the program if there is some trivial reason (based off of m) why there is no need to execute.
    $endgroup$
    – Christopher Mowla
    Mar 26 at 17:16










  • $begingroup$
    If you would like me to make a short video explanation of the algorithm (with an example), I can.
    $endgroup$
    – Christopher Mowla
    Mar 26 at 17:16












Your Answer





StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "387"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});






Christopher Mowla is a new contributor. Be nice, and check out our Code of Conduct.










draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathematica.stackexchange.com%2fquestions%2f193945%2fthe-most-efficient-algorithm-to-find-all-possible-integer-pairs-which-sum-to-a-g%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























2 Answers
2






active

oldest

votes








2 Answers
2






active

oldest

votes









active

oldest

votes






active

oldest

votes









16












$begingroup$

I think



IntegerPartitions[m, {2}, listOfIntegers]


does exactly what you want, and seems pretty efficient.






share|improve this answer









$endgroup$













  • $begingroup$
    Thanks! I have used IntegerPartitions for some Rubik's cube theory in the past (cycle types), but I didn't know that it can be used to select partitions from a custom list. I ran it and my algorithm on a larger data set than the largest listed on here, and my algorithm took 31 seconds, whereas IntegerPartitions took 16 seconds. Impressive. I originally wrote my algorithm as part of a coding interview at Wolfram Research, but they didn't hire me for the position. I guess I see why now. LOL.
    $endgroup$
    – Christopher Mowla
    Mar 25 at 21:52






  • 2




    $begingroup$
    @ChristopherMowla - But also, native functions use pre-compiled code, so have an advantage over your solution. See blog.wolfram.com/2011/12/07/…, especially the second point, if you'd like to optimize your code a bit for better comparison.
    $endgroup$
    – Andrew Cheong
    Mar 26 at 5:28


















16












$begingroup$

I think



IntegerPartitions[m, {2}, listOfIntegers]


does exactly what you want, and seems pretty efficient.






share|improve this answer









$endgroup$













  • $begingroup$
    Thanks! I have used IntegerPartitions for some Rubik's cube theory in the past (cycle types), but I didn't know that it can be used to select partitions from a custom list. I ran it and my algorithm on a larger data set than the largest listed on here, and my algorithm took 31 seconds, whereas IntegerPartitions took 16 seconds. Impressive. I originally wrote my algorithm as part of a coding interview at Wolfram Research, but they didn't hire me for the position. I guess I see why now. LOL.
    $endgroup$
    – Christopher Mowla
    Mar 25 at 21:52






  • 2




    $begingroup$
    @ChristopherMowla - But also, native functions use pre-compiled code, so have an advantage over your solution. See blog.wolfram.com/2011/12/07/…, especially the second point, if you'd like to optimize your code a bit for better comparison.
    $endgroup$
    – Andrew Cheong
    Mar 26 at 5:28
















16












16








16





$begingroup$

I think



IntegerPartitions[m, {2}, listOfIntegers]


does exactly what you want, and seems pretty efficient.






share|improve this answer









$endgroup$



I think



IntegerPartitions[m, {2}, listOfIntegers]


does exactly what you want, and seems pretty efficient.







share|improve this answer












share|improve this answer



share|improve this answer










answered Mar 25 at 18:10









RomanRoman

4,0871023




4,0871023












  • $begingroup$
    Thanks! I have used IntegerPartitions for some Rubik's cube theory in the past (cycle types), but I didn't know that it can be used to select partitions from a custom list. I ran it and my algorithm on a larger data set than the largest listed on here, and my algorithm took 31 seconds, whereas IntegerPartitions took 16 seconds. Impressive. I originally wrote my algorithm as part of a coding interview at Wolfram Research, but they didn't hire me for the position. I guess I see why now. LOL.
    $endgroup$
    – Christopher Mowla
    Mar 25 at 21:52






  • 2




    $begingroup$
    @ChristopherMowla - But also, native functions use pre-compiled code, so have an advantage over your solution. See blog.wolfram.com/2011/12/07/…, especially the second point, if you'd like to optimize your code a bit for better comparison.
    $endgroup$
    – Andrew Cheong
    Mar 26 at 5:28




















  • $begingroup$
    Thanks! I have used IntegerPartitions for some Rubik's cube theory in the past (cycle types), but I didn't know that it can be used to select partitions from a custom list. I ran it and my algorithm on a larger data set than the largest listed on here, and my algorithm took 31 seconds, whereas IntegerPartitions took 16 seconds. Impressive. I originally wrote my algorithm as part of a coding interview at Wolfram Research, but they didn't hire me for the position. I guess I see why now. LOL.
    $endgroup$
    – Christopher Mowla
    Mar 25 at 21:52






  • 2




    $begingroup$
    @ChristopherMowla - But also, native functions use pre-compiled code, so have an advantage over your solution. See blog.wolfram.com/2011/12/07/…, especially the second point, if you'd like to optimize your code a bit for better comparison.
    $endgroup$
    – Andrew Cheong
    Mar 26 at 5:28


















$begingroup$
Thanks! I have used IntegerPartitions for some Rubik's cube theory in the past (cycle types), but I didn't know that it can be used to select partitions from a custom list. I ran it and my algorithm on a larger data set than the largest listed on here, and my algorithm took 31 seconds, whereas IntegerPartitions took 16 seconds. Impressive. I originally wrote my algorithm as part of a coding interview at Wolfram Research, but they didn't hire me for the position. I guess I see why now. LOL.
$endgroup$
– Christopher Mowla
Mar 25 at 21:52




$begingroup$
Thanks! I have used IntegerPartitions for some Rubik's cube theory in the past (cycle types), but I didn't know that it can be used to select partitions from a custom list. I ran it and my algorithm on a larger data set than the largest listed on here, and my algorithm took 31 seconds, whereas IntegerPartitions took 16 seconds. Impressive. I originally wrote my algorithm as part of a coding interview at Wolfram Research, but they didn't hire me for the position. I guess I see why now. LOL.
$endgroup$
– Christopher Mowla
Mar 25 at 21:52




2




2




$begingroup$
@ChristopherMowla - But also, native functions use pre-compiled code, so have an advantage over your solution. See blog.wolfram.com/2011/12/07/…, especially the second point, if you'd like to optimize your code a bit for better comparison.
$endgroup$
– Andrew Cheong
Mar 26 at 5:28






$begingroup$
@ChristopherMowla - But also, native functions use pre-compiled code, so have an advantage over your solution. See blog.wolfram.com/2011/12/07/…, especially the second point, if you'd like to optimize your code a bit for better comparison.
$endgroup$
– Andrew Cheong
Mar 26 at 5:28













2












$begingroup$

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.






share|improve this answer








New contributor




Simon Erni is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






$endgroup$









  • 1




    $begingroup$
    You don't need to conduct any binary searches! Just make two simultaneous passes through the sorted list, one in increasing order and one in decreasing order. If the sum of the two scanned elements is less than $m$, increase the lower one; else decrease the higher one. Repeat until they meet in the middle. This is $O(n)$. (Of course the total complexity is still $O(nlog n)$ because of the sorting stage.)
    $endgroup$
    – TonyK
    Mar 26 at 14:21










  • $begingroup$
    @Simon, even though my code may look long, the majority of it is comments explaining the algorithm. If you are interested in knowing what I DID (not what I'm "trying to do") with my algorithm, start reading the comments from the line which states "The main idea of the algorithm is to find the point on numberline to begin selecting two number combinations which sum to m". All lines of code previous to that are for creating the list named numberLine and determining values of some booleans to end the program if there is some trivial reason (based off of m) why there is no need to execute.
    $endgroup$
    – Christopher Mowla
    Mar 26 at 17:16










  • $begingroup$
    If you would like me to make a short video explanation of the algorithm (with an example), I can.
    $endgroup$
    – Christopher Mowla
    Mar 26 at 17:16
















2












$begingroup$

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.






share|improve this answer








New contributor




Simon Erni is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






$endgroup$









  • 1




    $begingroup$
    You don't need to conduct any binary searches! Just make two simultaneous passes through the sorted list, one in increasing order and one in decreasing order. If the sum of the two scanned elements is less than $m$, increase the lower one; else decrease the higher one. Repeat until they meet in the middle. This is $O(n)$. (Of course the total complexity is still $O(nlog n)$ because of the sorting stage.)
    $endgroup$
    – TonyK
    Mar 26 at 14:21










  • $begingroup$
    @Simon, even though my code may look long, the majority of it is comments explaining the algorithm. If you are interested in knowing what I DID (not what I'm "trying to do") with my algorithm, start reading the comments from the line which states "The main idea of the algorithm is to find the point on numberline to begin selecting two number combinations which sum to m". All lines of code previous to that are for creating the list named numberLine and determining values of some booleans to end the program if there is some trivial reason (based off of m) why there is no need to execute.
    $endgroup$
    – Christopher Mowla
    Mar 26 at 17:16










  • $begingroup$
    If you would like me to make a short video explanation of the algorithm (with an example), I can.
    $endgroup$
    – Christopher Mowla
    Mar 26 at 17:16














2












2








2





$begingroup$

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.






share|improve this answer








New contributor




Simon Erni is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






$endgroup$



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.







share|improve this answer








New contributor




Simon Erni is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









share|improve this answer



share|improve this answer






New contributor




Simon Erni is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









answered Mar 26 at 10:07









Simon ErniSimon Erni

211




211




New contributor




Simon Erni is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.





New contributor





Simon Erni is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






Simon Erni is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.








  • 1




    $begingroup$
    You don't need to conduct any binary searches! Just make two simultaneous passes through the sorted list, one in increasing order and one in decreasing order. If the sum of the two scanned elements is less than $m$, increase the lower one; else decrease the higher one. Repeat until they meet in the middle. This is $O(n)$. (Of course the total complexity is still $O(nlog n)$ because of the sorting stage.)
    $endgroup$
    – TonyK
    Mar 26 at 14:21










  • $begingroup$
    @Simon, even though my code may look long, the majority of it is comments explaining the algorithm. If you are interested in knowing what I DID (not what I'm "trying to do") with my algorithm, start reading the comments from the line which states "The main idea of the algorithm is to find the point on numberline to begin selecting two number combinations which sum to m". All lines of code previous to that are for creating the list named numberLine and determining values of some booleans to end the program if there is some trivial reason (based off of m) why there is no need to execute.
    $endgroup$
    – Christopher Mowla
    Mar 26 at 17:16










  • $begingroup$
    If you would like me to make a short video explanation of the algorithm (with an example), I can.
    $endgroup$
    – Christopher Mowla
    Mar 26 at 17:16














  • 1




    $begingroup$
    You don't need to conduct any binary searches! Just make two simultaneous passes through the sorted list, one in increasing order and one in decreasing order. If the sum of the two scanned elements is less than $m$, increase the lower one; else decrease the higher one. Repeat until they meet in the middle. This is $O(n)$. (Of course the total complexity is still $O(nlog n)$ because of the sorting stage.)
    $endgroup$
    – TonyK
    Mar 26 at 14:21










  • $begingroup$
    @Simon, even though my code may look long, the majority of it is comments explaining the algorithm. If you are interested in knowing what I DID (not what I'm "trying to do") with my algorithm, start reading the comments from the line which states "The main idea of the algorithm is to find the point on numberline to begin selecting two number combinations which sum to m". All lines of code previous to that are for creating the list named numberLine and determining values of some booleans to end the program if there is some trivial reason (based off of m) why there is no need to execute.
    $endgroup$
    – Christopher Mowla
    Mar 26 at 17:16










  • $begingroup$
    If you would like me to make a short video explanation of the algorithm (with an example), I can.
    $endgroup$
    – Christopher Mowla
    Mar 26 at 17:16








1




1




$begingroup$
You don't need to conduct any binary searches! Just make two simultaneous passes through the sorted list, one in increasing order and one in decreasing order. If the sum of the two scanned elements is less than $m$, increase the lower one; else decrease the higher one. Repeat until they meet in the middle. This is $O(n)$. (Of course the total complexity is still $O(nlog n)$ because of the sorting stage.)
$endgroup$
– TonyK
Mar 26 at 14:21




$begingroup$
You don't need to conduct any binary searches! Just make two simultaneous passes through the sorted list, one in increasing order and one in decreasing order. If the sum of the two scanned elements is less than $m$, increase the lower one; else decrease the higher one. Repeat until they meet in the middle. This is $O(n)$. (Of course the total complexity is still $O(nlog n)$ because of the sorting stage.)
$endgroup$
– TonyK
Mar 26 at 14:21












$begingroup$
@Simon, even though my code may look long, the majority of it is comments explaining the algorithm. If you are interested in knowing what I DID (not what I'm "trying to do") with my algorithm, start reading the comments from the line which states "The main idea of the algorithm is to find the point on numberline to begin selecting two number combinations which sum to m". All lines of code previous to that are for creating the list named numberLine and determining values of some booleans to end the program if there is some trivial reason (based off of m) why there is no need to execute.
$endgroup$
– Christopher Mowla
Mar 26 at 17:16




$begingroup$
@Simon, even though my code may look long, the majority of it is comments explaining the algorithm. If you are interested in knowing what I DID (not what I'm "trying to do") with my algorithm, start reading the comments from the line which states "The main idea of the algorithm is to find the point on numberline to begin selecting two number combinations which sum to m". All lines of code previous to that are for creating the list named numberLine and determining values of some booleans to end the program if there is some trivial reason (based off of m) why there is no need to execute.
$endgroup$
– Christopher Mowla
Mar 26 at 17:16












$begingroup$
If you would like me to make a short video explanation of the algorithm (with an example), I can.
$endgroup$
– Christopher Mowla
Mar 26 at 17:16




$begingroup$
If you would like me to make a short video explanation of the algorithm (with an example), I can.
$endgroup$
– Christopher Mowla
Mar 26 at 17:16










Christopher Mowla is a new contributor. Be nice, and check out our Code of Conduct.










draft saved

draft discarded


















Christopher Mowla is a new contributor. Be nice, and check out our Code of Conduct.













Christopher Mowla is a new contributor. Be nice, and check out our Code of Conduct.












Christopher Mowla is a new contributor. Be nice, and check out our Code of Conduct.
















Thanks for contributing an answer to Mathematica Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathematica.stackexchange.com%2fquestions%2f193945%2fthe-most-efficient-algorithm-to-find-all-possible-integer-pairs-which-sum-to-a-g%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







Popular posts from this blog

Plaza Victoria

Puebla de Zaragoza

Musa