C/C++ Coding Exercise – Find Two Single Numbers

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?

Submit your solution: https://leetcode.com/problems/single-number-iii/

Using Map

You can use a map to have constant time in accessing, inserting, updating the elements. However, the space complexity is not constant. You would need two passes. The first pass increment the counter for each number and the second pass looks for count = 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        unordered_map<int, int> dict;
        for (int i = 0; i < nums.size(); i ++) {
            if (dict.count(nums[i])) {
                dict[nums[i]] ++;
            } else {
                dict[nums[i]] = 1;
            }
        }
        vector<int> r;
        for (int i = 0; i < nums.size(); i ++) {
            int cnt = dict[nums[i]];
            if (cnt == 1) { // we have a match
                r.push_back(nums[i]);                                
            }
        }        
        return r;
    }
};

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        unordered_map<int, int> dict;
        for (int i = 0; i < nums.size(); i ++) {
            if (dict.count(nums[i])) {
                dict[nums[i]] ++;
            } else {
                dict[nums[i]] = 1;
            }
        }
        vector<int> r;
        for (int i = 0; i < nums.size(); i ++) {
            int cnt = dict[nums[i]];
            if (cnt == 1) { // we have a match
                r.push_back(nums[i]);                                
            }
        }        
        return r;
    }
};

This solution gets accepted and the runtime is 36ms. The algorithm complexity is O(n).

XOR

The above solution works because we treat hash table is O(1) in looking-up and updating operation. We have not fully used all the critera in the description. For example, all other elements appear exactly twice. What does that tell you?.

We know that any number XOR itself becomes zero. And any number XOR zero doesn’t change. Therefore, if we XOR every number we will have a value that is equal to exactly A XOR B where A and B are the two numbers we are looking for.

So we know the XOR sum of these two numbers, if we look for a particular bit in one number, the corresponding bit should be opposite in another number. So based on this, we can group all numbers into two.

We can use n & (-n) to get the least significant bit in number n. Alternatively, n & (~(n – 1)) is also correct.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int n = nums.size();
        int r = 0;
        for (auto i: nums) {
            r ^= i;
        }
        vector<int> rtn(2, 0);
        int last = r & (-r);
        for (auto i: nums) {
            if (last & i) {
                rtn[0] ^= i;
            } else {
                rtn[1] ^= i;
            }
        }
        return rtn;
    }
};

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int n = nums.size();
        int r = 0;
        for (auto i: nums) {
            r ^= i;
        }
        vector<int> rtn(2, 0);
        int last = r & (-r);
        for (auto i: nums) {
            if (last & i) {
                rtn[0] ^= i;
            } else {
                rtn[1] ^= i;
            }
        }
        return rtn;
    }
};

This gets accepted in 16ms (almost twice as fast as the first approach). If you use n & (~(n – 1)) to get the least significant bit, it is slightly slower, which takes 20ms.

–EOF (The Ultimate Computing & Technology Blog) —