A math solution, O(n) time, O(1) space


  • 0
    Q

    The original set S = [s1, s2, ..., sn] should have the following properties:
    A1 = sum([s1, s2, ..., sn]) = 1 + 2 + ... + n = n * (n + 1) / 2
    A2 = sum([s1^2, s2^2, ..., sn^2]) = 1^2 + 2^2 + ... + n^2 = n * (n + 1) * (2 * n + 1) / 6
    Now element i of set S is missing and element j is duplicated, then:
    B1 = sum(S') = sum([s1', s2', ..., sn']) = 1 + 2 + ... + n - i + j = A1 - i + j
    B2 = sum([s1'^2, s2'^2, ..., sn'^2]) = 1^2 + 2^2 + ... + n^2 - i^2 + j^2 = A2 - i^2 + j^2
    So if we let:
    x1 = A1 - B1 = i - j
    x2 = (A2 - B2) / (A1 - B1) = (i^2 - j^2) / (i - j) = i + j
    We can actually solve i and j by:
    i = (x1 + x2) / 2
    j = (x1 - x2) / 2
    Where i is the number doesn't appear, and j is the number duplicated.


Log in to reply
 

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