package com.fishercoder.solutions;

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

/**136. Single Number

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?
*/

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);
        }
      }
      Iterator<Integer> it = set.iterator();
      return it.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;
    }
  }
}

@@ -132,16 +132,26 @@
 er%0A%0A
+ 
 Given a
-n
+ non-empty
  arr
@@ -237,14 +237,16 @@
 e.%0A%0A
+ 
 Note:%0A
+ 
 Your
@@ -347,16 +347,100 @@
  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%0Apub
@@ -1041,62 +1041,29 @@
     
-Iterator%3CInteger%3E it = set.iterator();%0A      return it
+return set.iterator()
 .nex

refactor 136