Given an array A[] and a number x, check for pair in A[] with sum as x

Question

LINQ/FP style:

Assert.IsTrue(new[] {1,2,3}.AnyPairSum(4));

Where:

static class LinqDemo
{
    public static bool AnyPairSum(this IEnumerable<int> source, int sum)
    {
        var a = source.OrderBy(i => i).ToArray();
        return scan(0, a.Length - 1);
        bool scan(int l, int r) =>
            l >= r ? false :
            a[l] + a[r] > sum ? scan(l, r - 1) :
            a[l] + a[r] < sum ? scan(l + 1, r) :
            true;
    }
}

Answer 1

Your algorithm isn't the most efficient out there.

As you process the input, you can keep track of the numbers you have already seen and which numbers would complement those to sum to x. For instance, in your example, x=4: You read 1, you know that if you encounter a x - 1 = 3, you have found a pair. Next you read a 2, you know that if you encounter a x - 2 = 2, you have found a pair. Then you encounter a 3, which we knew we needed earlier. We can return true.

In code:

public static bool AnyPairSumAlternative(this IEnumerable<int> source, int sum) {
  var complements = new HashSet<int>();
  foreach(var item in source) {
    if (complements.Contains(item)) {
      return true;
    }
    try {
      checked {
        complements.Add(sum - item);
      }
    } catch (OverflowException) {
      // If sum - item overflows, that means that no two ints together can sum to sum.
      // We swallow the exception and don't add anything to complements, since the complement
      // clearly doesn't exist within the data type.
    }
  }
  return false;
}

This approach skips out of the sorting, and loops through the input list only once. Checking for inclusion in the Hashset is \$O(1)\$, so if I'm not mistaken, this takes the solution from \$O(n\log n)\$ to \$O(n)\$.

As comment by @slepic points out, we need to be careful that sum - item doesn't overflow. If that happens, that automatically means that the complement cannot appear in the array, since it wouldn't fit in our datatype. To account for this, we can do the subtraction in checked context and catch any OverflowException.

Answer 2

As part of you regular testing, since you are using recursion, you should run this code at a large input that creates many nested calls. C# doesn't support require tail call optimization, therefore the code will throw a stack overflow error. To fix this, switch to the usual while loop.