Simple C++ solution


  • 18
    J

    class Solution
    {public:

    int singleNumber(vector<int>& nums) {
        
        for(int i = 1; i < nums.size(); ++i) nums[0] ^= nums[i];
        
        return nums[0];
        
    }
    

    };


  • 0
    R

    could you please explain how xor works here ??


  • 8
    C

    I will try to explain it here:
    the principle of excusive or operation is: if two bits are same, then result is 0, if two bits are not same(0,1 or 1,0) the result is 1. when you have two same numbers, say 9 and 9, the bitwise exclusive or operation: 1001^1001 is 0000.
    however, if you introduce another number say 3. we have 9,3,9. which in binary is 1001, 0011, 1001. if we do bitwise exclusive or operation starting from first number, we have:
    step 1: 1001^0011 = 1010
    step 2: 1010^1001 = 0011
    which the result is 3.
    the trick of using exclusive or here is that, when you encounter two same number, no matter how far they are apart from each other, excusive or will let them “counteract” each other.
    Let me know if you still dont understand.
    Chenxuan


  • 0
    J

    Cuichenxuan has made a very clear explanation. The idea is, xor a certain integer twice is equal to xor this integer with 0, which is itself. And it is independent of the sequence, because for the numbers that make even appearances, all the bit either (1)xor with 1 for even times, or (2)xor with 0 for even times, which in both cases will restore the bit to its original state, leaving the only integer that appeared odd times.


  • 0
    R

    Thank you so much. it cleared all my doubts. Highly appreciate it :)


  • 1
    J

    zhe ge tai niu le!


  • 0
    Y

    excellent!!excellent!!excellent!!excellent!!


  • 0
    Y

    @joe297 NB~~~~~~~~~


  • 0
    M

    just:a ⊕ b ⊕ a = b?


  • 0
    O

    The solution makes me astonished. Very excellent!!!!


  • 0
    F

    This requires the vector to be sorted first, right?


  • 0
    F

    @frankliuao Uh, apparently not.


  • 0
    J

    amazing. The best answer I've seen.


  • 0
    H

    excellent. two xor operations cancel each other.


Log in to reply
 

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