# Math solution using C, O(1) space, O(n) time

• ``````/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
int* findErrorNums(int* nums, int numsSize, int* returnSize) {
int i, dm1 = 0, dm2 = 0, sum, A, B;
for (i = 1; i <= numsSize; i ++) {
dm1 += nums[i-1] - i;
dm2 += nums[i-1]*nums[i-1] - i*i;
}
sum = dm2 / dm1;
A = (sum - dm1) / 2;
B = (sum + dm1) / 2;
int *ret = (int*) malloc(sizeof(int) * 2);
ret[0] = B;
ret[1] = A;
*returnSize = 2;
return ret;
}

``````

O(1) space.
O(n) time, assuming multiplication is constant time.

Explanation.

For any multiset of numbers, two things are invariant under rearrangement of elements:

• sum of elements (I call it m1)
• sum of squares of elements (... m2)

(there are more invariants, but we don't need them now.)

If we change an element from a to b, then:

• sum of elements changes by b - a (= dm1)
• sum of squares of elements changes by b^2 - a^2 (= dm2)

Using dm1 and dm2, we can find that b + a = dm2 / dm1. Then we can solve for a and b.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.