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

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.