Find sum of integer array without overflow

Question

Given an array of integers (positive and negative), each having at most K bits (plus the sign bit), and it is known that the sum of all the integers in the array also has at most K bits (plus the sign bit). Design an algorithm that computes the sum of integers in the array, with all intermediate sums also having at most K bits (plus the sign bit). [Hint: find in what order you should add positive and negative numbers].

This is a question from interview material not a homework

I am actually thinking of creating two separate arrays one for positive and other for negative, sort both of them and then add both so that most negative gets added to most positive... But this seems to have O(nlogn) time complexity(to sort) and O(n) space complexity> Please help!

Answer 1

The main idea is to iterate the array with two indexes: for positive and negative elements. When the sum is negative we will search for next positive element (using corresponding iterator) to add to the sum, otherwise - for the negative one.

This code should work:

public final class ArrayAdder {
  @NotNull
  private final int[] array;

  private int sum;

  public ArrayAdder(@NotNull int[] array) {
    this.array = array;
  }

  public int sum() {
    sum = 0;

    final IntPredicate positive = v -> v > 0;
    final Index positiveIndex = new Index(positive);
    final Index negativeIndex = new Index(positive.negate());

    while (positiveIndex.index < array.length || negativeIndex.index < array.length) {
      sum += sum < 0 ? sum(positiveIndex, negativeIndex) : sum(negativeIndex, positiveIndex);
    }

    return sum;
  }

  private int sum(@NotNull Index mainIndex, @NotNull Index secondaryIndex) {
    int localSum = 0;
    // searching for the next suitable element
    while (mainIndex.index < array.length && secondaryIndex.sign.test(array[mainIndex.index])) {
      mainIndex.index++;
    }

    if (mainIndex.index < array.length) {
      localSum += array[mainIndex.index++];
    } else {
      // add the remaining elements
      for (; secondaryIndex.index < array.length; secondaryIndex.index++) {
        if (secondaryIndex.sign.test(array[secondaryIndex.index])) {
          localSum += array[secondaryIndex.index];
        }
      }
    }
    return localSum;
  }

  private static final class Index {
    @NotNull
    private final IntPredicate sign;

    private int index;

    public Index(@NotNull IntPredicate sign) {
      this.sign = sign;
    }
  }
}

Answer 2

First note that even if you let the immediate results overflow, the final result will always be correct if it can be represented. This is because integral types of any size act like cyclic groups under addition in most languages including Java (not in C, where integer overflow is undefined behavior, and C#, which is able to throw you an overflow exception).

If you still want to prevent overflow, here's how to perform it in-place and in linear time:

• split the array in-place to its negative entries (in any order) and to its positive entries (in any order). Zero can end up anywhere. In other words, perform one quick-sort step with the pivot being zero.

• Let ni point to the start of the array (where negative entries are located).

• Let pi point to the end of the array.
• Let sum be zero.

• While pi >= ni

  • if sum is negative
    • add arr[pi] to the sum.
    • if arr[pi] is negative (we've run out of positive addends) and sum is positive (an overflow has occured), the result overflows.
    • decrement pi
  • else
    • add arr[ni] to the sum.
    • if arr[ni] is positive and sum is negative, the result overflows.
    • increment ni.

• Finally, check if sum has more than K bits. If it does, declare the result overflows.

Answer 3

Option 1: Sort the array in-place and iterate over half of it. At every step, add the ith element with the size-i-1th element.

Doesn't work if there's a few large numbers but many small negative numbers (or vice versa).

Option 2 (improvement):

Sort in-place.

Keep two indexes - one at the start and one at the end. Exit a loop when they meet. At every step if the result so far is negative add the value at the second index and advance it. If the result is positive add the value at the first index and advance it.