Point out potential overflow bugs

Question

Here's my solution to interviewbit problem. link

You are given a read only array of n integers from 1 to n. Each integer appears exactly once except A which appears twice and B which is missing. Return A and B. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? Note that in your output A should precede B. N <= 10^5

It looks like there's an overflow problems somewhere. Could you point out such places and suggest fixes.

  typedef long long int unit;

vector<int> Solution::repeatedNumber(const vector<int> &A) {
    unit n = A.size();
    unit sum = n*(n+1)/2;
    unit sumsq = n*(n+1)*(2*n+1)/6;
    unit arrsum = std::accumulate(A.begin(), A.end(), 0);


    unit arrsq = 0;
    for(int item : A) {
        arrsq += (unit)item*item;
    }

    unit c1 = arrsum - sum;

    unit c2 = arrsq - sumsq;

    unit a = (c2/c1 + c1);
    a/=2;

    unit b = (c2/c1 - c1);
    b/=2;

    return {a, b};
}

P.S It gotta be overflow problem because the same solution works in Python.

Update Here's solution provided by authors of a problem. It's interesting how he fights the overflow problem in summation by subtracting.

 class Solution {
public:
    vector<int> repeatedNumber(const vector<int> &V) {
       long long sum = 0;
       long long squareSum = 0;
       long long temp;
       for (int i = 0; i < V.size(); i++) {
           temp = V[i];
           sum += temp;
           sum -= (i + 1);
           squareSum += (temp * temp);
           squareSum -= ((long long)(i + 1) * (long long)(i + 1));
       }
       // sum = A - B
       // squareSum = A^2 - B^2 = (A - B)(A + B)
       // squareSum / sum = A + B
       squareSum /= sum;

       // Now we have A + B and A - B. Lets figure out A and B now. 
       int A = (int) ((sum + squareSum) / 2);
       int B = squareSum - A;

       vector<int> ret;
       ret.push_back(A);
       ret.push_back(B);
       return ret;
    }
};

Answer 1

The problem is this:

unit arrsum = std::accumulate(A.begin(), A.end(), 0);

You need to use 0LL to make it accumulate the values as long long.

Code that demonstrates the problem:

int main()
{
    vector<int> A;
    for (int i = 0; i < 1000000; ++i)
        A.push_back(1000000);

    long long arrsum = accumulate(A.begin(), A.end(), 0LL);
    cout << arrsum;

    return 0;
}

Outputs -727379968 without the LL and the correct result with it.

Note that you can also use accumulate to compute the sum of squares:

unit arrsq = accumulate(A.begin(), A.end(), 0LL, 
                             [](unit x, unit y) { return x + y*y; });

Answer 2

The potential overflow problems are:

unit sum = n*(n+1)/2;

here the maximum n value is 10^5. Hence, n*(n+1) will yield 10^10 and then computes the division due to operator precedence.

The second place is

unit sum = n*(n+1)(2*n+1)/6;

the intermediate value computed here goes upto 10^15.

Also there is integer overflow in the where you are computing the sum of squares of all the numbers.