O(n) time, O(1) space, one pass, no hashmap, no xor


  • 0
    J

    I use golang, but the code is easy to understand for any one, just a little math.

    func findErrorNums(nums []int) []int {
        n := len(nums)                      // x for missed number, and y for twiced number
        a := n * (n+1) / 2                  // a = 1 + 2 + ... + n
        b := n * (n+1) * (2*n+1) / 6        // b = 1*1 + 2*2 + ... + n*n
        for _, i := range nums{
            a -= i
            b -= i * i
        }                                   // a = x - y, b = x*x - y*y
        b /= a                              // b = x + y
        a = (a+b) / 2                       // a = y
        b = b - a                           // b = x
        return []int{b, a}
    }
    

Log in to reply
 

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