Accepted code with proper Explaination. Does anyone have a better idea?


  • 117
    D

    The code makes use of 2 variables.

    ones - At any point of time, this variable holds XOR of all the elements which have
    appeared "only" once.
    twos - At any point of time, this variable holds XOR of all the elements which have
    appeared "only" twice.

    So if at any point time,

    1. A new number appears - It gets XOR'd to the variable "ones".
    2. A number gets repeated(appears twice) - It is removed from "ones" and XOR'd to the
      variable "twos".
    3. A number appears for the third time - It gets removed from both "ones" and "twos".

    The final answer we want is the value present in "ones" - coz, it holds the unique element.

    So if we explain how steps 1 to 3 happens in the code, we are done.
    Before explaining above 3 steps, lets look at last three lines of the code,

    common_bit_mask = ~(ones & twos)

    ones & = common_bit_mask

    twos & = common_bit_mask

    All it does is, common 1's between "ones" and "twos" are converted to zero.

    For simplicity, in all the below explanations - consider we have got only 4 elements in the array (one unique element and 3 repeated elements - in any order).

    Explanation for step 1

    Lets say a new element(x) appears.

    CURRENT SITUATION - Both variables - "ones" and "twos" has not recorded "x".

    Observe the statement "twos| = ones & x".
    Since bit representation of "x" is not present in "ones", AND condition yields nothing. So "twos" does not get bit representation of "x".
    But, in next step "ones ^= x" - "ones" ends up adding bits of "x". Thus new element gets recorded in "ones" but not in "twos".

    The last 3 lines of code as explained already, converts common 1's b/w "ones" and "twos" to zeros.
    Since as of now, only "ones" has "x" and not "twos" - last 3 lines does nothing.

    Explanation for step 2.

    Lets say an element(x) appears twice.

    CURRENT SITUATION - "ones" has recorded "x" but not "twos".

    Now due to the statement, "twos| = ones & x" - "twos" ends up getting bits of x.
    But due to the statement, "ones ^ = x" - "ones" removes "x" from its binary representation.

    Again, last 3 lines of code does nothing.
    So ultimately, "twos" ends up getting bits of "x" and "ones" ends up losing bits of "x".

    Explanation for step 3.

    Lets say an element(x) appears for the third time.

    CURRENT SITUATION - "ones" does not have bit representation of "x" but "twos" has.

    Though "ones & x" does not yield nothing .. "twos" by itself has bit representation of "x". So after this statement, "two" has bit representation of "x".
    Due to "ones^=x", after this step, "one" also ends up getting bit representation of "x".

    Now last 3 lines of code removes common 1's of "ones" and "twos" - which is the bit representation of "x".
    Thus both "ones" and "twos" ends up losing bit representation of "x".

     class Solution {
        public:
        // Let us take the example of {3, 3, 2, 3} to understand this
            int singleNumber(int A[], int n) {
                int ones=0, twos =0;
                int common_bit_mask;
                for(int i=0; i<n;i++)
                {
                     /* The expression "one & arr[i]" gives the bits that are
                   there in both 'ones' and new element from arr[].  We
                   add these bits to 'twos' using bitwise OR
         
                   Value of 'twos' will be set as 0, 3, 3 and 1 after 1st,
                   2nd, 3rd and 4th iterations respectively */
                   
                    twos= twos|(ones&A[i]);
                    /* XOR the new bits with previous 'ones' to get all bits
                   appearing odd number of times
         
                   Value of 'ones' will be set as 3, 0, 2 and 3 after 1st,
                   2nd, 3rd and 4th iterations respectively */
                    ones=ones^A[i];
                     /* The common bits are those bits which appear third time
                   So these bits should not be there in both 'ones' and 'twos'.
                   common_bit_mask contains all these bits as 0, so that the bits can 
                   be removed from 'ones' and 'twos'   
         
                   Value of 'common_bit_mask' will be set as 00, 00, 01 and 10
                   after 1st, 2nd, 3rd and 4th iterations respectively */
                    common_bit_mask= ~(ones&twos);
                    /* Remove common bits (the bits that appear third time) from 'ones'
                     
                   Value of 'ones' will be set as 3, 0, 0 and 2 after 1st,
                   2nd, 3rd and 4th iterations respectively */
                    ones &=common_bit_mask;
                    /* Remove common bits (the bits that appear third time) from 'twos'
         
                   Value of 'twos' will be set as 0, 3, 1 and 0 after 1st,
                   2nd, 3rd and 4th itearations respectively */
                    twos &=common_bit_mask;
                }
                return ones;
            }
        };

  • 0
    D

    best explanation


  • 0
    D

    Thank u @diego2 :)


  • 0

    Hey @Deepalaxmi,

    Welcome to DIscuss. Thanks for sharing such thoughtful analysis. Keep up the good work!


  • 0
    Z

    One of the best explanations I've ever met.


  • 0
    C

    thanks. very nice explanation.


  • 0
    W
    This post is deleted!

  • 0
    D

    very clear explanation


  • 0
    E

    Thank you very much!


  • 0
    D
    This post is deleted!

  • 0
    D

    a very nice explanation, i have read it twice. thx


  • 0
    S

    Really helpful, thank you.


  • 0
    D

    Very Nice Explanation. Out of all the answers posted for this solution filtered with highest number of votes, this is by far the best explained solution. All the others, despite having more votes are extremely difficult to understand. Play with this solution with a small example like 5,5,5,7 ...ans is 7.


  • 0
    L

    Thank you very much. This is the best explanation I have ever seen!


  • 0
    H

    Simple and concise. Thank you.


  • 0
    G

    great explanation . Thanks


  • 0
    X

    Excellent Solution


  • 1
    R

    great explaination!!!! Please can you tell if we can extend it to general solution for eg 4,5... occurrence?


Log in to reply
 

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