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;
}
};
The problem is this:
You need to use
0LL
to make it accumulate the values aslong long
.Code that demonstrates the problem:
Outputs
-727379968
without theLL
and the correct result with it.Note that you can also use
accumulate
to compute the sum of squares: