CODEWITHSUNDEEP
calgorithm
irappa
irappa

Reputation: 749

handling large numbers and overflows

I am given an array of N elements and I need to find the index P within this array where sum of values in the rage 0 to P is equal to sum of values in the range P+1 to N-1.

The values of each element in the array can range to -2147483648 to 2147483647 and N can be max 10000000.

Given this how do I ensure there is no overflow when adding each values to find the index P ?

Upvotes: 2

Views: 476

Answers (3)

chux
chux

Reputation: 153447

To insure no overflow, use int32_t and int64_t.

The range of values [-2147483648 ... 2147483647] matches the int32_t range. You could also use int64_t for this, but an array of 10000000 deserves space considerations.

As the sum of any 10,000,000 values does not exceed the range of int64_t, perform all your additions using int64_t.

#include <stdint.h>
size_t foo(const int32_t *value, size_t N) {
  int64_t sum = 0;
  ...
  sum += value[i];
  ...
}

BTW: Confident that a solution can be had that does not require addition 64-bit addition.
[Edit] Failed to derive simple int32_t only solution, but came up with:

size_t HalfSum(const int32_t *value, size_t N) {
  // find sum of entire array    
  int64_t ArraySum = 0;
  size_t P;
  for (P = 0; P < N; P++) {
    ArraySum += value[P];
  }

  // compute sum again, stopping when it is half of total
  int64_t PartialSum = 0;
  for (P = 0; P < N; P++) {
    PartialSum += value[P];
    if ((PartialSum * 2) == ArraySum) {
      return P;
    }
  }

  return N;  // No solution (normally P should be 0 ... N-1)
}

Upvotes: 4

cmaster - reinstate monica
cmaster - reinstate monica

Reputation: 40614

Use 64 bit integers for your calculations. The best type to use is int64_t since long is no guaranteed to be 64 bits (you have to #include <stdint.h> to make it available).

Edit: Pascal Cuoq is right: long long does provide the 64-bit guarantee as well and doesn't need an include (it can be longer than 64 bits, though), so it's just the long type that you have to avoid if you want to be portable.

Upvotes: 1

KrisSodroski
KrisSodroski

Reputation: 2842

In the worst case scenario, P+1 = N-1. Since the max value of an ynumber can only be 2147483647 or -2147483647 for any single number, It means that in the worst cases possible, P would be the max or min of long. In the other cases, P will still be a long integer. Because of this, you should only need to use a long in the worst case scenario (since if your worse case expected outcome is that P is the largest possible number that any single number can be is a long.

To make sure you don't have to use anything larger, pair up negative values with postive ones so that you stay below the overflow of a long.

Imagine we have 3 numbers, a b and c. If a + b overflows the long datatype, we know that c will not be P.

Now imagine that we have 4 numbers, a, b, c, d such that a + b + c = d (meaning d is P), if a + b would overflow long, it means 1) c cannot be P 2) there is a combination of a + b + c such that the data type of long would not need to be overflowed.

For instance, a is max long, b is max long, c is min long, and d is 0, then a + c + b = d would be the correct combination of operations in order to not use a data type larger than long, and we can try a + c because we know c cannot be P since a + b would overflow long > maximum possible value of P.

Upvotes: -1

Related Questions