CODEWITHSUNDEEP
c++arraysalgorithm
user1373317
user1373317

Reputation: 116

Summing up numbers in an array

Suppose I have an array of N non-negative integers, each of which can be very large (0->100,000). Let us also suppose that N can very large (~100,000,000).

For an array [a0 a1 ... aN-1], I would like to write a function which returns the sum of (-2)^ai for the entire array. I would like to have O(n*log(n)) time complexity and O(n) space.

For example, take [1 2 3] -- this would return (-2)^1 + (-2)^2 + (-2)^3 = -6 Another constraint is that for answers exceeding 100,000,000, the function should return -1;

A naive (but wrong) solution is the following:

    int solve(vector<int> &A) {
      int answer = 0;
      for (auto iter = A.begin(); iter != A.end(); ++iter) {
        answer += pow(-2, *iter);
      }
      return (answer <= 1e8) ? answer : -1;
    }

This doesn't work b/c answer will overflow for values > 31 (assuming that the native signed integer size is 4 bytes). Using longs also doesn't work b/c that breaks for values in the array greater than 63.

A high-level solution I can think of is to sort the array using std::sort and to then walk it. For values in the array which are greater than 31, we factor out some multiple of 31 by subtracting from the values in the array. This is acceptable b/c we are dealing with sums of exponents. I was curious if there are known, O(n*log(n)) complexity, O(n) space solutions to this problem.

Upvotes: 1

Views: 135

Answers (2)

Alexander Anikin
Alexander Anikin

Reputation: 1098

An idea...

Your function answers 2 questions:

1) Does result fit in 100M limit 2) What is the sum of items lower than 100M

You don't have to calculate the latter if 1) is not satisfied, so final count can care less about if something fits in int or not.

To make things easier we can use count sort and sum counts. Let's make array counts that will hold multiplier for 2^(i), so the final sum will be sum(counts[i]*2^i). Not that counts does not use sign flip-flop, we have to put appropriate signs when filling it.

Now we can do reduction in counts array. Note, that if counts[i] > 2, then sum will be the same for array modified as following:

  • counts[i]-2
  • counts[i+1]+1

The same is applicable for negative sign as well. So, in one loop from 0 to max of counts we can reduce values in counts leaving only 0 and 1/-1 in each value.

As you know, value of 2^N index is bigger than sum of anything that be accumulated in 0..2^N-2 values for at least 2 times. So if your highest index (after reduction) is bigger than 28 (2^28=268,435,456), then result will not fit into 100,000,000.

Now, if 1) is pased, you know the final and temporary result is not bigger than 268,435,456, so it will fit in int type, so just do your math and check final result again.

Upvotes: 0

MBo
MBo

Reputation: 80287

Note that (-2)^K has vary simple binary representation: it is ..00001000.. for even K and ..1111110000.. for odd K (2's complement).

So you can create array (int or boolean) for accumulating the sum in binary representation. It's length should be determined through max value from array (with overhead depending on N - about Log2(N) cells).

Then walk through array and just add binary representation of current number to accumulator. Example for array A=[2,3,4]

value(K)     binary(-2)^K   accum
                           00000000    
2            100           00000100
3            11111000      11111100 
4            00010000      00001100

Every add operation takes Max(A)+Log2(N) elementary ops

Possible mini-optimization - sort input array and group repeated values. For example, if array contains 8 value of 4, one could easily take 8*(-2)^4= 10000 << 3 = 10000000 in single shift operation without 7 add operations.

Upvotes: 1

Related Questions