1
\$\begingroup\$

Is this the optimal algorithm to satisfy this problem?

It does work. I get the: 1 and 5 (or 5 and 1) as 1 + 9 = 10.


Here's a function that, when passed a list and a target sum, returns two distinct zero-based indices of any two of the numbers, whose sum is equal to the target sum. If there are no two numbers, the function should return null.

For example, FindTwoSum(new List() { 3, 1, 5, 7, 5, 9 }, 10) should return a Tuple containing any of the following pairs of indices:

  • 0 and 3 (or 3 and 0) as 3 + 7 = 10
  • 1 and 5 (or 5 and 1) as 1 + 9 = 10
  • 2 and 4 (or 4 and 2) as 5 + 5 = 10

Someone had suggested the following, but I was not sure how to code it.

Order the data. Start at the left and the right at the same time. Add the left most and the right most entries. If the total is too high, move from the right towards the center. If the total is too low, move from the left towards the center.

So I came up with the following. It has 3 loop constructs though.


namespace AlgorithmFind2Sum
{
    class TwoSum
    {
        public static void Main(string[] args)
        {
            // This set of data will find a match that adds up to the sum.
            Tuple<int, int> indices = FindTwoSum(new List<int>() { 3, 1, 5, 7, 5, 9 }, 10);

            // This set of data will NOT find a match that adds up to the sum.
            //Tuple<int, int> indices = FindTwoSum(new List<int>() { 1, 2, 4, 5, 7, 7 }, 10);

            if (indices != null)
            {
                // Write.
                Console.WriteLine("Entry that added up to the sum: " + indices.Item1 + " " + indices.Item2);

                // Reads the next line.
                Console.ReadLine();
            }
            else
            {
                // Write.
                Console.WriteLine("None added up to the sum.");

                // Reads the next line.
                Console.ReadLine();
            }
        }

        public static Tuple<int, int> FindTwoSum(IList<int> list, int sum)
        {
            //++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
            // Order the data - sort it.
            //++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

            // Using LINQ OrderBy method (it will generate new List<int> with items sorted):
            var orderedList = list.OrderBy(x => x).ToList();

            string finished = "N";
            string found = "N";
            string firstOuterLoopEntry = "Y";
            int outerLoopCount = 0;
            int innerLoopCount = 0;
            int loopUpperBound = list.Count - 1;
            int SumOfTwo = 0;

            // Loops as long as the condition is true.
            while (finished == "N")
            {
                while (outerLoopCount < orderedList.Count)
                {
                    innerLoopCount = 0;

                    while (innerLoopCount < loopUpperBound)
                    {
                        if (firstOuterLoopEntry == "Y")
                        {
                            SumOfTwo = orderedList[outerLoopCount] + orderedList[innerLoopCount + 1];

                            if (SumOfTwo == sum)
                            {
                                found = "Y";
                                break;
                            }
                        }
                        else
                        {
                            // Set the loop upper bound here again in that I have to make up for skipping the entry that is itself.
                            loopUpperBound = orderedList.Count;

                            // Do not process the entry that is itself.
                            if (innerLoopCount != outerLoopCount)
                            {
                                SumOfTwo = orderedList[outerLoopCount] + orderedList[innerLoopCount];

                                if (SumOfTwo == sum)
                                {
                                    found = "Y";
                                    break;
                                }
                            }
                        }

                        innerLoopCount = innerLoopCount + 1;
                    }

                    if (found == "Y")
                    {
                        finished = "Y";
                        break;
                    }
                    else
                    {
                        firstOuterLoopEntry = "N";

                        outerLoopCount = outerLoopCount + 1;
                    }
                }

                finished = "Y";
            }

            // Return.
            if (found == "Y")
            {
                return Tuple.Create(orderedList[outerLoopCount], orderedList[innerLoopCount + 1]);
            }
            else
            {
                return null;
            }
        }
    }
}
\$\endgroup\$
2
\$\begingroup\$

You sort but don't use the sort. Not getting why you need to reset loopUpperBound = orderedList.Count; Just start with that. Don't use Y N - use a Boolean. You are potentially evaluating each pair twice.

It is pretty simple:

public static Tuple<int, int> GetPair(List<int> ints, int sum)
{
    int upperIndex = ints.Count - 1;
    int lowerIndex = 0;
    ints.Sort();
    while (lowerIndex < upperIndex)
    {
        int curSum = ints[lowerIndex] + ints[upperIndex];
        if (curSum == sum)
        {
            return new Tuple<int, int>(ints[lowerIndex], ints[upperIndex]);
        }
        if (curSum < sum)
        {
            lowerIndex++;
        }
        else
        {
            upperIndex--;
        }
    }
    return null;
}

If you want to brute force it:

public static Tuple<int, int> GetPairBrute(List<int> ints, int sum)
{
    for (int i = 0; i < ints.Count - 1; i++)
    {
        for (int j = i + 1; j < ints.Count; j++)
        {
            if (ints[i] + ints[j] == sum)
            {
                return new Tuple<int, int>(ints[i], ints[j]);
            }
        }
    }
    return null;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Actually I do use the sorted list. Which becomes: 1,3,5,5,7,9 for the "find a match" test case and 1,2,4,5,7,7 for the "NOT find a match" test case. \$\endgroup\$ – user3020047 Jul 11 '18 at 17:11
  • \$\begingroup\$ However, I really do not need to sort the list after all. \$\endgroup\$ – user3020047 Jul 11 '18 at 17:45
  • \$\begingroup\$ Your brute force approach, for the "NOT find a match" test case, reduces down the number of entries processed in the 2nd pass and beyond. It's goes 5, then 4, then 3, then 2, then 1. My approach, for the "NOT find a match" test case, does not reduce down the number of entries processed. It's 5 processed each pass. For the "find a match" test case, we both are the same with regard to processing - 1 pass. So your solution is more efficient for sure. \$\endgroup\$ – user3020047 Jul 11 '18 at 17:53
  • \$\begingroup\$ The pretty simple approach seems to be the best and efficient. Starting at the left and the right at the same time. Add the left most and the right most entries. If the total is too high, move from the right towards the center. If the total is too low, move from the left towards the center. \$\endgroup\$ – user3020047 Jul 11 '18 at 18:40
  • \$\begingroup\$ Lastly, the line int loopUpperBound = List.Count - 1; should have been int loopUpperBound = orderedList.Count - 1; My mistake. \$\endgroup\$ – user3020047 Jul 11 '18 at 19:05

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.