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}}}
$\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
16
$\begingroup$

I think

IntegerPartitions[m, {2}, listOfIntegers]

does exactly what you want, and seems pretty efficient.

$\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.

$\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(n\log 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

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.