Repository: keon/algorithms
Pull request #260 (2018-04-27 23:09:44)

add single_number3: find two elements that appear only once
Interesting problem I solved today :)
Single number series is actually really good for practicing bitwise operations, especially XOR.

danghai: It is interesting question! I come up with another problem being harder. Find the two elements that appear only one. All the other elements may appear twice, thrice, ... ^^
SaadBenn: Can we not do this with a dict? Loop through the list and add the count. Then loop again and return the result whose count is 1. Time complexity would be `O(2n)` == `O(n)` @keon 
keon: @SaadBenn 
That would be the best answer if there is no constraint.
but in this case using dict will make the space complexity O(N). we want O(1)

keon: @danghai we would need a different approach then because XOR wouldn't work for numbers appearing odd number of times.



Patch:
diff --git a/README.md b/README.md
index a2ce964..7c22931 100644
--- a/README.md
+++ b/README.md
@@ -69,8 +69,9 @@ For running all tests write down:
     - [find_missing_number](bit/find_missing_number.py)
     - [power_of_two](bit/power_of_two.py)
     - [reverse_bits](bit/reverse_bits.py)
-    - [single_number2](bit/single_number2.py)
     - [single_number](bit/single_number.py)
+    - [single_number2](bit/single_number2.py)
+    - [single_number3](bit/single_number3.py)
     - [subsets](bit/subsets.py)
     - [add_bitwise_operator](bit/add_bitwise_operator.py)
     - [bit_operation](bit/bit_operation.py)
diff --git a/bit/single_number3.py b/bit/single_number3.py
new file mode 100644
index 0000000..5182bd2
--- /dev/null
+++ b/bit/single_number3.py
@@ -0,0 +1,49 @@
+"""
+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.
+Limitation: Time Complexity: O(N) and Space Complexity O(1)
+
+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.
+
+
+Solution:
+1. Use XOR to cancel out the pairs and isolate A^B
+2. It is guaranteed that at least 1 bit exists in A^B since
+   A and B are different numbers. ex) 010 ^ 111 = 101
+3. Single out one bit R (right most bit in this solution) to use it as a pivot
+4. Divide all numbers into two groups.
+   One group with a bit in the position R
+   One group without a bit in the position R
+5. Use the same strategy we used in step 1 to isolate A and B from each group.
+"""
+
+
+def single_number3(nums):
+    """
+    :type nums: List[int]
+    :rtype: List[int]
+    """
+    # isolate a^b from pairs using XOR
+    ab = 0
+    for n in nums:
+        ab ^= n
+
+    # isolate right most bit from a^b
+    right_most = ab & (-ab)
+
+    # isolate a and b from a^b
+    a, b = 0, 0
+    for n in nums:
+        if n & right_most:
+            a ^= n
+        else:
+            b ^= n
+    return [a, b]


Test patch:
diff --git a/tests/test_bit.py b/tests/test_bit.py
index c9bafea..33d80d9 100644
--- a/tests/test_bit.py
+++ b/tests/test_bit.py
@@ -5,6 +5,7 @@ from bit.power_of_two import is_power_of_two
 from bit.reverse_bits import reverse_bits
 from bit.single_number import single_number
 from bit.single_number2 import single_number2
+from bit.single_number3 import single_number3
 from bit.subsets import subsets
 from bit.bit_operation import get_bit, set_bit, clear_bit, update_bit
 from bit.swap_pair import swap_pair
@@ -121,6 +122,12 @@ class TestSuite(unittest.TestCase):
         random.shuffle(nums)
         self.assertEqual(single, single_number2(nums))
 
+    def test_single_number3(self):
+        self.assertEqual(sorted([2,5]),
+                         sorted(single_number3([2, 1, 5, 6, 6, 1])))
+        self.assertEqual(sorted([4,3]),
+                         sorted(single_number3([9, 9, 4, 3])))
+
     def test_subsets(self):
 
         self.assertSetEqual(subsets([1, 2, 3]),