Accepted C++/Java O(n)-time O(1)-space Easy Solution with Detail Explanations


  • 491

    Once again, we need to use XOR to solve this problem. But this time, we need to do it in two passes:

    • In the first pass, we XOR all elements in the array, and get the XOR of the two numbers we need to find. Note that since the two numbers are distinct, so there must be a set bit (that is, the bit with value '1') in the XOR result. Find
      out an arbitrary set bit (for example, the rightmost set bit).

    • In the second pass, we divide all numbers into two groups, one with the aforementioned bit set, another with the aforementinoed bit unset. Two different numbers we need to find must fall into thte two distrinct groups. XOR numbers in each group, we can find a number in either group.

    Complexity:

    • Time: O (n)

    • Space: O (1)

    A Corner Case:

    • When diff == numeric_limits<int>::min(), -diff is also numeric_limits<int>::min(). Therefore, the value of diff after executing diff &= -diff is still numeric_limits<int>::min(). The answer is still correct.

    C++:

    class Solution
    {
    public:
        vector<int> singleNumber(vector<int>& nums) 
        {
            // Pass 1 : 
            // Get the XOR of the two numbers we need to find
            int diff = accumulate(nums.begin(), nums.end(), 0, bit_xor<int>());
            // Get its last set bit
            diff &= -diff;
    
            // Pass 2 :
            vector<int> rets = {0, 0}; // this vector stores the two numbers we will return
            for (int num : nums)
            {
                if ((num & diff) == 0) // the bit is not set
                {
                    rets[0] ^= num;
                }
                else // the bit is set
                {
                    rets[1] ^= num;
                }
            }
            return rets;
        }
    };
    

    Java:

    public class Solution {
        public int[] singleNumber(int[] nums) {
            // Pass 1 : 
            // Get the XOR of the two numbers we need to find
            int diff = 0;
            for (int num : nums) {
                diff ^= num;
            }
            // Get its last set bit
            diff &= -diff;
            
            // Pass 2 :
            int[] rets = {0, 0}; // this array stores the two numbers we will return
            for (int num : nums)
            {
                if ((num & diff) == 0) // the bit is not set
                {
                    rets[0] ^= num;
                }
                else // the bit is set
                {
                    rets[1] ^= num;
                }
            }
            return rets;
        }
    }
    

    Thanks for reading :)


    Acknowledgements:

    • Thank @jianchao.li.fighter for introducing this problem and for your encouragement.

    • Thank @StefanPochmann for your valuable suggestions and comments. Your idea of diff &= -diff is very elegent! And yes, it does not need to XOR for both group in the second pass. XOR for one group suffices. I revise my code accordingly.

    • Thank @Nakagawa_Kanon for posting this question and presenting the same idea in a previous thread (prior to this thread).

    • Thank @caijun for providing an interesting test case.


  • 2

    Great code! Nice usage of accumulate :-) diff &= ~(diff - 1) is also elegant!


  • 48

    Just a bit shorter, using -diff instead of ~(diff - 1) and indexing instead of if-else.

    vector<int> singleNumber(vector<int>& nums) {
        int diff = accumulate(nums.begin(), nums.end(), 0, bit_xor<int>());
        diff &= -diff;
        vector<int> rets(2, 0);
        for (int num : nums)
            rets[!(num & diff)] ^= num;
        return rets;
    }
    

    The accumulate doesn't save code, btw:

        int diff = 0; for (int num : nums) diff ^= num;
        int diff = accumulate(nums.begin(), nums.end(), 0, bit_xor<int>());
    

    It's also about 10% slower. Wrapping each of the above in a 1000-loop, the accumulate-solution then takes about 360 ms and the loop-solution about 322 ms (both up from 20 ms).


  • 0

    brilliant idea!


  • 1

    Awesome codes! I revise my code accordingly. Thanks very much!


  • 1

    Wow, Stefan. You can always come up with concise and elegant ways of doing the same thing, like the indexing rets[!(num & diff)].


  • 5
    S

    Can Any body explain what is "set bit"? What is "last set bit"? Thanks.


  • 12
    C

    "set bit" means bit "1", "last set bit" means the right most bit "1".


  • 0
    C

    Stefan always plays magic!


  • 0
    S

    @caikehe Thank you very much. But why do we need to get the right most bit? How it can help us in solving this problem. Sorry I can't see it.


  • 1
    C

    I think you should complete these two (https://leetcode.com/problems/single-number/) (https://leetcode.com/problems/single-number-ii/) first, in order to get some sense about what is Bit Manipulation.


  • 0
    C

    @steven10, sorry, you means you can not see the question? Give me your email address~


  • 0
    S

    Haha, I can see the problem. But I can't see the exact reason behind the method for using the right most bit. I've finished those two problems, but still can not totally undertand this. Could you explain it with more details?


  • 22

    Hi, steven10. I think using the rightmost 1-bit is just for ease of coding (diff &= -diff will leave the rightmost 1-bit). In fact, you can use any 1-bit. This 1-bit implies that the two single numbers are different at this bit. Then we use this bit to split all the remaining numbers into two groups. Suppose the two single numbers are a and b and they differ in the third bit (a is 1 at this bit while b is 0). After splitting, numbers with 1 in the third bit will fall in the group of a while the remaining ones fall in the group of b. Till now, we will be able to get a and b via a simple within-group xor.


  • 0
    S

    Thanks for your much more detailed explanation. I makes more sense to me now. I just wonder how you guys come up with diff &= -diff. It is not quite readable. The person who mentiond in the first reply "diff = diff & ~(diff-1)" is actually more readable. Thoug it also didn't make any sense to me at first. Thanks bro!


  • 4

    It is actually not easy to realize that ~(diff - 1) == -diff. You may refer to the Two's complement.


  • 0
    S

    Thanks a lot. Very good reference. It's very helpful.


  • 0
    C

    Elegant solution.

    However, there's a bug in the code and I don't think test cases catch it here. If the two distinct number are 0 and 2^(-31), diff &= -diff will overflow, which makes diff to be 0. In this way it will only return [0, 0], which is wrong.

    To solve this issue, you may do something like:

    diff = diff == Integer.MIN_VALUE ? Integer.MIN_VALUE : diff & -diff; (in java).


  • 1

    Hi, caijun. How could an int be 2 ^ (-31) (I am assuming that you use ^ to mean power)? If 2 ^ (-31) is 2 xor -31, then it is just -29.


  • 0
    C

    Oops, my bad. I mean Integer.MIN_VALUE -2^31 (2 to power of 31).


Log in to reply
 

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