Sharing explanation of the solution


  • 290

    If you were stuck by this problem, it's easy to find a solution in the discussion. However, usually, the solution lacks some explanations.

    I'm sharing my understanding here:

    The two numbers that appear only once must differ at some bit, this is how we can distinguish between them. Otherwise, they will be one of the duplicate numbers.

    One important point is that by XORing all the numbers, we actually get the XOR of the two target numbers (because XORing two duplicate numbers always results in 0). Consider the XOR result of the two target numbers; if some bit of the XOR result is 1, it means that the two target numbers differ at that location.

    Let’s say the at the ith bit, the two desired numbers differ from each other. which means one number has bit i equaling: 0, the other number has bit i equaling 1.

    Thus, all the numbers can be partitioned into two groups according to their bits at location i.
    the first group consists of all numbers whose bits at i is 0.
    the second group consists of all numbers whose bits at i is 1.

    Notice that, if a duplicate number has bit i as 0, then, two copies of it will belong to the first group. Similarly, if a duplicate number has bit i as 1, then, two copies of it will belong to the second group.

    by XoRing all numbers in the first group, we can get the first number.
    by XoRing all numbers in the second group, we can get the second number.


  • 0
    H

    you enlightened me!


  • 0
    S

    really helpful, thanks!


  • 0
    J

    Hi douglasleer,

    Would you explain more? What if those two distinct numbers are 3 (0011) and 12 (1100), then they are 2 bits different from each other. How are things going then?


  • 1

    for 3 and 12, there are actually 4 bits different. all the four bits.
    By xoring all the numbers, we get 1111. We can choose any one of the 4 different bits; it doesn't change the final result.

    For general cases, we use the first bit or the last bit that differs to partition the numbers into two groups. It is because, we may not have a second bit or second-last bit that differs.


  • 0
    X

    Hi @douglasleer, thanks for sharing. But I am still a little confused about the partition. Say for example, 3(011) and 5(101) are the two numbers that need to be returned. Then the diff would be 110 coming out of XOR. If the last bit of diff(0 here) is the bit chosen for partition, both of 3 and 5 would go to the same group since their last bit(1) is different with diff's(0)?


  • 0

    The diff bit should be the 1 (either the first 1, or the second). If the bit of XOR is 0, it means their bits (at that location) do not differ.


  • 0
    C

    Thanks for your explain! This really helps!


  • 0
    A

    Thanks for the explanation!


  • 0
    X

    clever and helpful explainations!

    Many thanks!


  • 0
    R

    The approach is really great but one thing I am confused about is how do you determine which bit to partition them based on. Since you don't know which two numbers are different, you don't know which bit they differ on, so how do you determine which bit to partition all the numbers based on?


  • 2
    X

    @rajveer_90hotmail.com
    firstly, we got the result of XOR ALL elements, say it's a variable called result. then we got the least significant "set" bit of the result by:

    result&=-result (recall how to represent two's complement in computer)

    like if the result is 101, then we changed it to 001 using above equation. It means that the two single numbers start to differ from the least significant bit;

    then we can divide all numbers into two group
    by checking the least significant bit. Then XOR all numbers in each of the two groups we can get the two single numbers respectively.


  • 0
    R

    @XiaoYu_zju Thanks a ton! That really helps.


  • 0

    @rajveer_90hotmail.com I just added the 4th paragraph.


  • 0
    S

    @douglasleer Thank you very much for detailed explanation


  • 0
    K

    thanks a lott!!


  • 4
    public int[] singleNumber(int[] nums) {
            int temp = 0;
            for (int n : nums) {
                temp ^= n;
            }
            int mask = -temp & temp;
    
            int single1 = 0, single2 = 0;
            for (int num : nums) {
                if ((num & mask) == 0) {
                    single1 ^= num;
                } else {
                    single2 ^= num;
                }
            }
            return new int[] {single1, single2};
        }
    

  • 6
    L

    There is a little trick here to get a bit equal 1 from the result XOR.
    see if we get XOR = aaaa1000(a = 1 or 0)
    we could get the first(from low to high) bit equals 1 as follow:
    first:~XOR = bbbb0111 (b = ~a)
    then add 1, with carrying bits ~XOR + 1 = bbbb1000
    then, XOR & (~XOR + 1) = 00001000
    so we can write as XOR & (-XOR) also.


  • 0
    H

    really helpful.


  • 0
    M

    So brilliant!


Log in to reply
 

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