Solution to the "Is the Sum S?" Algorithm Puzzle

[This is a solution to the Is the sum S? algorithm puzzle posted earlier]

A description of the problem:

Given n numbers in the range [-M,M], and a target sum S, also in the range [-M, M], can you figure out in O(n) time, whether those n numbers add up to S, while keeping all your computations within the [-M, M] range? (M is unknown to you). Assume arithmetic operations are O(1).

Solution

---

Since the numbers are in the range [-M,M], the key observation we use is that adding a positive number to a negative number (or vice versa) will not overflow.

Thus we do the following:

Start with running sum = the negative of the target. Now we try to add the elements of the array to this running sum, hoping to see whether we get a zero in the end.

If the running sum is negative, add a positive number to it. If there are no positive numbers left in the array, then we know we cannot end with a total sum of 0.

If the running sum is positive, add a negative number to it. If there are no negative numbers left in the array, then we know we cannot end with a total sum of 0.

If the running sum is zero, add a positive or negative, does not matter.

Here is what a C++ implementation might look like (untested):

bool has_sum(const std::vector<int>& a, int target) {
  // Technically, the negation is a bug 
  // and overflow is possible here.
  // The range of int in C++ is actually 
  // [-M-1, M], not [-M, M].
  // But, we ignore that...
  int sum = -target;

  std::vector<int> positives;
  std::vector<int> negatives;
  int total = 0;

  // Collect the positive and negative numbers.
  for (auto x : a) {
    if (x > 0) {
      positives.push_back(x);
      total++;
    }
    if (x < 0) {
      negatives.push_back(x);
      total++;
    }
  }

  int positives_seen = 0;
  int negatives_seen = 0;

  // Note: no overflow in the + here :-)
  while (positives_seen + negatives_seen < total) {
    if (sum < 0) {
      // If sum is negative, try to add a positive.
      if (positives_seen >= positives.size()) {
        break;
      }
      sum += positives[positives_seen++];
    } else if (sum > 0) {
      // If sum is positive, try to add a negative.
      if (negatives_seen >= negatives.size()) {
        break;
      }
      sum += negatives[negatives_seen++];
    } else {
      // If sum is zero pick a positive.
      if (positives_seen < positives.size()) {
        sum += positives[positives_seen++];
      } else {
        // There is at least one negative left.
        sum += negatives[negatives_seen++];
      }
    }
  }

  return sum == 0;
}