How to use bit manipulation to solve this problem?


  • 8
    G

    Here's the question.

    Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
    
    For example:
    
    Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].
    
    **Note**:
    The order of the result is not important. So in the above example, [5, 3] is also correct.
    Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
    

    I know how to do this with a hashtable, but it's more than constant space.

    I've read this post using bit manipulation, but found it hard to understand why. Can anyone kindly elaborate on that?

    Many Thanks!


  • 0
    A

    I would also like an explanation.


  • 30
    G

    I did some research online.

    The idea is to xor all the numbers, while two identical numbers will result in "0" with xor, so the final results will be xor of the "two numbers only showing once, e.g.(A and B) ".

    A^ B may look like this "0110...0010". The bit with "1" there is for sure coming from a "0" from A, and a "1" coming from B. Let's take bit No.1 as an example("0110...00->1<-0"), we can group all the numbers by bit No.1 as "0", and bit No.1 as "1". After grouping, we are sure that A and B are in the two groups separately.

    Again, we do a xor within each group. Each group has a set of numbers appearing twice and one of A and B. So after xor on every group, we get A and B separately.

    Hope it helps.


  • 0
    J

  • 0
    A

    The Explanation link is elaborate. Wish I could upvote the comment :)


Log in to reply
 

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