Single Number III

  • 3

    Given an array of integers, every element appears twice except for two. Find that single two.

    Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

    If you know the xor method of the "Single Number I", please think about the properties of xor of the two numbers.

    //Best solution:

    1. x = xor of each element in the list ==> x = a xor b
    2. a != b => there are at least one 1-bit in x
    3. take an arbitrary 1-bit (which means a and b is different on this bit), the elements in the array can be classified into two groups: one of them contains a, the other contains b.
    4. a = xor of each element in the list which the corresponding bit = 0
    5. b = a xor x

Log in to reply

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