package com.fishercoder.solutions;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

/**136. Single Number

 Given a non-empty 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?

 Example 1:
 Input: [2,2,1]
 Output: 1

 Example 2:
 Input: [4,1,2,1,2]
 Output: 4
*/

public class _136 {

  public static class Solution1 {
    /**
     * 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(int[] nums) {
      Set<Integer> set = new HashSet();
      for (int i : nums) {
        if (!set.add(i)) {
          set.remove(i);
        }
      }
      return set.iterator().next();
    }
  }

  public static class Solution2 {
    /**
     * 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(int[] nums) {
      int res = 0;
      for (int i : nums) {
        res ^= i;
      }
      return res;
    }
  }
}

@@ -109,339 +109,8 @@
 t;%0A%0A
-/**136. Single Number%0A%0A Given a non-empty array of integers, every element appears twice except for one. Find that single one.%0A%0A Note:%0A Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?%0A%0A Example 1:%0A Input: %5B2,2,1%5D%0A Output: 1%0A%0A Example 2:%0A Input: %5B4,1,2,1,2%5D%0A Output: 4%0A*/%0A%0A
 publ
@@ -126,16 +126,18 @@
 _136 %7B%0A%0A
+  
   public
@@ -162,16 +162,20 @@
 tion1 %7B%0A
+    
     /**%0A
@@ -171,32 +171,36 @@
        /**%0A     
+  
+  
 * Approach 1: us
@@ -281,16 +281,20 @@
 ce%0A     
+  
+  
 * and on
@@ -383,16 +383,20 @@
 t,%0A     
+ 
+   
 * O(n) t
@@ -486,16 +486,20 @@
 be%0A     
+    
 * more e
@@ -536,27 +536,35 @@
 tions.%0A     
-*/%0A
+    */%0A    
     public i
@@ -589,24 +589,30 @@
 t%5B%5D nums) %7B%0A
+      
       Set%3CIn
@@ -635,24 +635,30 @@
  HashSet();%0A
+      
       for (i
@@ -680,16 +680,24 @@
         
+   
+     
 if (!set
@@ -703,24 +703,34 @@
 t.add(i)) %7B%0A
+          
           se
@@ -742,16 +742,24 @@
 ove(i);%0A
+        
         
@@ -756,24 +756,30 @@
           %7D%0A
+      
       %7D%0A    
@@ -776,24 +776,30 @@
     %7D%0A      
+ 
+     
 return set.i
@@ -824,15 +824,23 @@
     
+   
+ 
 %7D%0A
+  
   %7D%0A%0A
+  
   pu
@@ -869,28 +869,36 @@
 tion2 %7B%0A    
+  
+  
 /**%0A
+    
      * Appro
@@ -991,16 +991,20 @@
 ck%0A     
+  
+  
 * here: 
@@ -1095,16 +1095,20 @@
 ne%0A     
+    
 * that a
@@ -1127,27 +1127,35 @@
  once.%0A     
+ 
-*/%0A
+   */%0A    
     public i
@@ -1180,24 +1180,30 @@
 t%5B%5D nums) %7B%0A
+      
       int re
@@ -1211,24 +1211,30 @@
  = 0;%0A      
+  
+    
 for (int i :
@@ -1234,32 +1234,40 @@
 int i : nums) %7B%0A
+        
         res %5E= i
@@ -1270,26 +1270,38 @@
 %5E= i;%0A      
+   
-%7D%0A
+   %7D%0A      
       return
@@ -1310,16 +1310,22 @@
 es;%0A    
-%7D%0A
+    %7D%0A  
   %7D%0A%7D%0A

refactor 136