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


  • 0
    1
    /**
     * 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.


Log in to reply
 

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