Single Number

fishercoder1534 · fishercoder1534 · commit c5d5a52ca276 · 2016-08-04T18:46:13.000-07:00
diff --git a/MEDIUM/src/medium/SingleNumber.java b/MEDIUM/src/medium/SingleNumber.java
@@ -0,0 +1,45 @@
+package medium;
+
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.Set;
+
+/**136. Single Number  QuestionEditorial Solution  My Submissions
+Total Accepted: 141879
+Total Submissions: 277792
+Difficulty: Medium
+Given an array of integers, every element appears twice except for one. Find that single one.
+
+Note:
+Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
+
+Hide Company Tags Palantir Airbnb
+Hide Tags Hash Table Bit Manipulation
+Hide Similar Problems (M) Single Number II (M) Single Number III (M) Missing Number (H) Find the Duplicate Number
+*/
+public class SingleNumber {
+    //approach 1: use set, since this problem explicitly states that every element appears twice and only one appears once
+    //so, we could safely remove the ones that are already in the set, O(n) time and O(n) space.
+    //HashTable approach works similarly like this one, but it could be more easily extend to follow-up questions.
+    public int singleNumber_using_set(int[] nums) {
+        Set<Integer> set = new HashSet();
+        for(int i : nums){
+            if(!set.add(i)) set.remove(i);
+        }
+        Iterator<Integer> it = set.iterator();
+        return it.next();
+    }
+    
+
+    //approach 2: bit manipulation, use exclusive or ^ to solve this problem:
+    //we're using the trick here: every number ^ itself will become zero, so, the only remaining element will be the one that
+    //appeared only once.
+    public int singleNumber_using_bit(int[] nums) {
+        int res = 0;
+        for(int i : nums){
+            res ^= i;
+        }
+        return res;
+    }
+
+}
