bgabbasov
BAN USERinput: array A[1..n]
The idea is to use the sum of inegers from 1 to n and the sum of squares of integers from 1 to n:
sum1 = sum from k = 1 to n (k) = n(n+1)2
sum2 = sum from k = 1 to n (k^2) = n(2n+1)(n+1)/6
Then we are calculating
s1 = sum1 - sum from k=1 to n (A[k])
s2 = sum2 - sum from k=1 to n (A[k]^2)
Now we have the system of equations:
a-b = s1
a^2-b^2 = s2
where a is missing value and b is duplicate.
The solution is:
a = (s2 + s1^2)/(2 s1)
b = (s2 - s1^2)/(2 s1)
The complexity of the algorith is O(n).
The code:
void f(int n)
{
int sum1 = n*(n+1)/2;
int sum2 = n*(2*n+1)*(n+1)/6;
for(int i=0; i<n; i++)
{
int next = readnext(); // get next value
sum1 -= next;
sum2 -= next*next;
}
int a = (sum2+sum1*sum1)/(2*sum1);
int b = (sum2-sum1*sum1)/(2*sum1);
printf("Missing: %d\nDuplicate: %d\n", a, b);
}
The system of equations if followed from:
- bgabbasov January 02, 2013sum from k = 1 to n (k) - a + b = Sum from k = 1 to n (A[k])
and
sum from k = 1 to n (k^2) - a^2 + b^2 = Sum from k = 1 to n (A[k]^2)
a is a missing value, and b is a duplicate