Clever Geek Handbook

Find the sum of an integer array without overflow

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

This is a question from interview material, not homework.

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

+3


source to share


3 answers


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

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



  • splits the array into its negative entries (in any order) and its positive entries (in any order). Zero can end anywhere. In other words, do one quicksort step when the axis of rotation is zero.

  • Let it ni

    point to the beginning of the array (where the negative entries are located).

  • Let it pi

    point to the end of the array.
  • Let it sum

    be zero.

  • Until pi >= ni

    • if sum

      negative
      • add arr[pi]

        to sum

        .
      • if arr[pi]

        negative (we have run out of positive additions), and sum

        positive (overflow occurred), the result overflows.
      • decrement pi

    • yet
      • add arr[ni]

        to sum

        .
      • if arr[ni]

        positive and sum

        negative, the result overflows.
      • increment ni

        .

  • Finally, check if the sum

    bit has more than K

    . If so, declare a result overflow.

+7


source


The basic idea is to iterate over the array with two indices: for positive and negative elements. When the sum is negative, we will look for the next positive element (using the appropriate iterator) to add to the sum, otherwise, for negative.

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;
    }
  }
}
+2


source


Option 1: Sort the array in place and iterate over half of it. At each step, add a i

th element with a size-i-1

th element .

Doesn't work if there are several large numbers but many small negative numbers (or vice versa).

Option 2 (improvement):

Sorting in place.

Keep two indices, one at the beginning and one at the end. Get out of the loop when they meet. At each step, if the result is still negative, add the value to the second index and advance it. If the result is positive, add the value to the first index and advance it.

0


source






More articles:


All Articles