# Single Number III Solutions in C++

Number 260

Difficulty Medium

Acceptance 64.4%

Link LeetCode

Other languages Go

## Solutions

### C++ solution by haoel/leetcode

// Source : https://leetcode.com/problems/single-number-iii/// Author : Hao Chen// Date : 2016-01-16/** For the problem - only one number appears once when all other numbers appears exactly twice.** We know, we can XOR all of the array elements. Since X^X is zero, and X^0 is X,* so all of the duplicated number will zero themselves out, and the only number would be the result.** However, this solution cannot be applied directly to finding two numbers that appear once each.** Suppose that these numbers that appear once are X and Y, and all other numbers appear twice.* If we decide to XOR all the array's elements, the overall result would actually be `X^Y`.** Unfortunately, there is no way to extract J and K out of their XOR.** But since X and Y are different, we are sure that X^Y is different than zero.** This information is valuable in sense that we know pieces of information that differ.* If we pick up any bit that is 1 in X XOR Y, we can use it as a mask to test each element of the array.** Obviously, that mask will be the discriminator between X and Y -** Only one of them will have value 1 at that particular position.*** Now that we have the mask with exactly one bit set to 1, we can walk through the array once again.** But this time we are going to maintain two XORed results.** - One for numbers that have bit 1 at the mask's position* - Another for numbers that have bit 0 at that position** In this way, we are sure that all duplicates will go into the same pile.** But likewise, we are sure that X and Y will go into separate piles.** So, the overall result is that* - the first XORed result will be equal to X* - and the second XORed result will be equal to Y**/class Solution {public:vector<int> singleNumber(vector<int>& nums) {int allxor = 0;for (int n : nums) {allxor ^= n;}int mask = 1;while ( (mask & allxor) == 0 ) {mask <<= 1;}int zero = 0;int one = 0;for (int n : nums) {if (n & mask ){one ^= n;}else {zero ^= n;}}vector<int> result;result.push_back(zero);result.push_back(one);return result;}};