Update single-number-iii.cpp

kamyu104 · kamyu104 · commit 2ca73e508cca · 2015-09-03T00:19:04.000+08:00
diff --git a/C++/single-number-iii.cpp b/C++/single-number-iii.cpp
@@ -2,6 +2,25 @@
 // Space: O(1)
 
 class Solution {
+public:
+    vector<int> singleNumber(vector<int>& nums) {
+        // Xor all the elements to get x ^ y.
+        int x_xor_y = accumulate(nums.cbegin(), nums.cend(), 0, bit_xor<int>());
+        // Get the last bit where 1 occurs.
+        x_xor_y &= -x_xor_y;
+
+        // Get the subset of A where the number has the bit.
+        // The subset only contains one of the two integers, call it x.
+        // Xor all the elemets in the subset to get x.
+        vector<int> result(2, 0);
+        for (const auto& i : nums) {
+            result[!(i & x_xor_y)] ^= i;
+        }
+        return result;
+    }
+};
+
+class Solution2 {
 public:
     vector<int> singleNumber(vector<int>& nums) {
         // Xor all the elements to get x ^ y.
