O(n) time, no bit manipulation, no HashSet, no swap. Just math.


  • 0
    G

    Just two simple math equations:
    a^2 - b^2 = delta2
    a - b = delta
    So we have:
    a = (delta2 / delta + delta) / 2;
    b = (delta2 / delta - delta) / 2;
    Note: since the given array size will in the range [2, 10000], we can safely use int.
    Here is code:

    public int[] findErrorNums(int[] nums) {
        int n = nums.length, delta = 0, delta2 = 0;
        for (int i = 0; i < n; i++) {
            delta2 += nums[i]*nums[i] - (i+1)*(i+1);
            delta += nums[i] - (i+1);
        }
        return new int[] {(delta2 / delta + delta) / 2, (delta2 / delta - delta) / 2};
    }
    

Log in to reply
 

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