package com.fishercoder.solutions;

import java.util.HashMap;
import java.util.Map;

/**
 * 137. Single Number II

Given an array of integers, every element appears three times 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 _137 {

  public static class Solution1 {
    public int singleNumber(int[] nums) {
      Map<Integer, Integer> map = new HashMap();
      for (int i : nums) {
        map.put(i, map.getOrDefault(i, 0) + 1);
      }
      for (int key : map.keySet()) {
        if (map.get(key) != 3) {
          return key;
        }
      }
      return 0;
    }
  }

  public static class Solution2 {
    /** Credit: https://discuss.leetcode.com/topic/11877/detailed-explanation-and-generalization-of-the-bitwise-operation-method-for-single-numbers/2 */
    public int singleNumber(int[] nums) {
      int counter1 = 0;
      int counter2 = 0;
      int mask = 0;
      for (int num : nums) {
        counter2 ^= counter1 & num;
        counter1 ^= num;
        mask = ~(counter1 & counter2);
        counter1 &= mask;
        counter2 &= mask;
      }
      return counter1;
    }
  }
}

@@ -82,255 +82,8 @@
 p;%0A%0A
-/**%0A * 137. Single Number II%0A%0AGiven an array of integers, every element appears three times except for one. Find that single one.%0A%0ANote:%0AYour algorithm should have a linear runtime complexity. Could you implement it without using extra memory?%0A*/%0A
 publ
@@ -99,16 +99,18 @@
 _137 %7B%0A%0A
+  
   public
@@ -135,16 +135,20 @@
 tion1 %7B%0A
+    
     publ
@@ -187,16 +187,22 @@
 %7B%0A      
+   
+   
 Map%3CInte
@@ -234,32 +234,38 @@
 ashMap();%0A      
+    
+  
 for (int i : num
@@ -261,32 +261,40 @@
 int i : nums) %7B%0A
+        
         map.put(
@@ -327,26 +327,38 @@
 + 1);%0A      
+   
-%7D%0A
+   %7D%0A      
       for (i
@@ -390,16 +390,24 @@
         
+     
+   
 if (map.
@@ -419,24 +419,34 @@
 ey) != 3) %7B%0A
+          
           re
@@ -459,26 +459,40 @@
 ey;%0A        
+ 
+       
 %7D%0A
+      
       %7D%0A    
@@ -489,24 +489,30 @@
     %7D%0A      
+ 
+     
 return 0;%0A  
@@ -517,15 +517,23 @@
     
+  
+  
 %7D%0A  
+ 
+ 
 %7D%0A%0A
+  
   pu
@@ -570,10 +570,25 @@
     
-/*
+    /**%0A         
 * Cr
@@ -730,12 +730,25 @@
 rs/2
- */%0A
+%0A         */%0A    
     
@@ -781,24 +781,30 @@
 t%5B%5D nums) %7B%0A
+      
       int co
@@ -817,24 +817,30 @@
  = 0;%0A      
+ 
+     
 int counter2
@@ -847,24 +847,30 @@
  = 0;%0A      
+  
+    
 int mask = 0
@@ -867,24 +867,30 @@
 t mask = 0;%0A
+      
       for (i
@@ -906,32 +906,40 @@
 nums) %7B%0A        
+   
+     
 counter2 %5E= coun
@@ -946,24 +946,32 @@
 ter1 & num;%0A
+        
         coun
@@ -991,16 +991,24 @@
         
+ 
+       
 mask = ~
@@ -1030,32 +1030,40 @@
 nter2);%0A        
+       
+ 
 counter1 &= mask
@@ -1064,32 +1064,40 @@
 = mask;%0A        
+      
+  
 counter2 &= mask
@@ -1100,26 +1100,38 @@
 mask;%0A      
+     
+ 
 %7D%0A
+      
       return
@@ -1145,16 +1145,22 @@
 r1;%0A    
-%7D%0A
+    %7D%0A  
   %7D%0A%7D%0A

refactor 137