12
\$\begingroup\$

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;
    }
}
\$\endgroup\$
12
\$\begingroup\$

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.

\$\endgroup\$
  • 4
    \$\begingroup\$ Be aware that ints can underflow and overflow and the method should check for that. For example now it would yield true for sum=Int64.MinValue and the enumerator containing [Int64.MaxValue, 1], but Int64.MinValue is definitely not sum of the two. \$\endgroup\$ – slepic Nov 7 at 8:05
  • \$\begingroup\$ @slepic good point. Thanks. I edited to account for this. \$\endgroup\$ – JAD Nov 7 at 8:35
  • \$\begingroup\$ @slepic I don't believe ints can underflow \$\endgroup\$ – Ryan M Nov 7 at 19:19
  • \$\begingroup\$ @RyanM hmm, I guess underflow was confused with overflow at the negative side. \$\endgroup\$ – JAD Nov 8 at 7:18
  • 1
    \$\begingroup\$ On the other hand, I think we all understand what was meant, so it's kinda splitting hairs either way. \$\endgroup\$ – JAD Nov 8 at 19:06
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Yep, just tried to practice FP approach as stated in the question. C# is very far from to be really multi-paradigm language. The most missing parts for me are tail recursion (everything looks a way cleaner using it) and primary constructors (how I wish to have syntactically cheap classes to represent closures!). \$\endgroup\$ – Dmitry Nogin Nov 7 at 17:28
  • 1
    \$\begingroup\$ "C# doesn't support tail call optimization" is wrong, particularly since RyuJit actually does exactly that optimization in some cases. What is true is that the language does not require TCO. \$\endgroup\$ – Voo Nov 8 at 20:36

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.