// 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 Solution {
    // HashMap version, O(n) + O(n) = O(n) time. O(n) space.
    // public int singleNumber(int[] A) {
    //     HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

    //     for(int i : A){
    //     	map.put(i, map.containsKey(i)? map.get(i) + 1 : 1);
    //     }

    //     for(int i : map.keySet()){
    //     	if(map.get(i) == 1){
    //     		return i;
    //     	}
    //     }

    //     return 0;
    // }

    // Bit manipulation version. O(n) time, O(1) space.
	public int singleNumber(int[] A) {
		// absorb singular bits, i.e. this var keeps bits info of elements that has shown up only once,
		// if same elem came second time, its bits info are cleard and stored in var 'twos'. Similarly, if same
		// elem show up for the third time, 'ones' will store this occurrence, while previous two occurs are
		// stored in 'twos', combining bits info in 'ones' and 'twos' will tell us whether elements have shown
		// up three times.
        int ones = 0;
        // only store bits info of elems that have shown up twice.
        int twos = 0;
        // only store bits info of elems that have shown up three times.
        int threes = 0;
        // tmp var that store bits of elems that show up for the second time.
        int one2two = 0;

        for(int i : A){
        	one2two = i & ones;
        	twos |= one2two;
        	// XOR clear the same bits, so if bits of same element show up twice, the bits info of that
        	// element will be abandoned.
        	ones ^= i;
             //if both once and twice(once &twice) saved a certain bit,it means this bit appears three times.
            threes= ~(ones&twos);
            //clear the bit locations which appear three times
            ones &= threes;
            twos &= threes;
        }
        return ones;
    }
}

@@ -777,549 +777,547 @@
 %7B%0A%09%09
-// absorb singular bits, i.e. this var k
+int ones = 0;%0A        int twos = 0;%0A        int thr
 ee
-p
 s 
-bits info of elements that has shown up only once,%0A%09%09// if same elem came second time, its bits info are cleard and stored in var 'twos'. Similarly, if same%0A%09%09// elem show up for the third time, 'ones' will store this occurrence, while previous two occurs are%0A%09%09// stored in 'twos', combining bits info in 'ones' and 'twos' will tell us whether elements have shown%0A%09%09// up three times.
+= 0;%0A        int one2two = 0;%0A%0A        for(int i : A)%7B%0A            one2two = i & ones;%0A            twos = twos %7C one2two;%0A            ones %5E= i;%0A            threes = (ones & twos);%0A            ones = ones&(~threes);%0A            twos = twos&(~threes);%0A        %7D%0A        return ones;
 %0A    
-    int ones = 0;%0A        // only store bits info of elems that have shown up twice.%0A        int twos = 0;
+%7D%0A%7D%0A%0Apublic class Solution %7B%0A    public int singleNumber(int%5B%5D A) %7B%0A        // look at all the numbers from a bitwise perspective,%0A        // iterate over all integers, we extract the bits info and 
 %0A   
@@ -1327,198 +1327,345 @@
   //
- only
  store 
-bits info of elems that have shown up three times.%0A        int threes = 0;%0A        // tmp var that store bits of elem
+them in three variables:%0A        // ones: all bits that appear once so far.%0A        // twos: bits appear twice so far.%0A        // threes: bits appear three times so far.%0A        // we keep update bits info, at last, one
 s 
-t
 ha
-t show up for the second time.%0A        int one2
+ve value of the single number.%0A        int ones = 0;%0A        int 
 two
+s
  = 0;%0A
+        int threes = 0;%0A        
 %0A   
@@ -1676,345 +1676,391 @@
  for
+ 
 (int i 
-: A)%7B%0A        %09one2two = i & ones;%0A        %09twos %7C= one2two;%0A        %09// XOR clear the same bits, so if bits of same element show up twice, the bits info of that%0A        %09// element will be abandoned.%0A        %09ones %5E= i;%0A             //if both once and twice(once &twice) saved a certain bit,it means this bit appears three times.
+= 0; i %3C A.length; i++) %7B%0A            // ones %5E= num;%0A            // 1 + 1 = 2;%0A            // 1 + 2 = 3;%0A            // which bits info to update first:%0A            // XOR on ones will lose info of carry. so we update twos first, then %0A            // update ones, update threes based on ones and twos.%0A            twos = twos %7C (ones & A%5Bi%5D);%0A            ones = ones %5E A%5Bi%5D;
 %0A   
@@ -2078,22 +2078,22 @@
 rees
+ 
 = 
-~(
 ones
-&
+ & 
 twos
-)
 ;%0A  
@@ -2108,16 +2108,17 @@
   //
+ 
 clear th
 e bi
@@ -2117,48 +2117,37 @@
 r th
-e bit locati
+rees bits from 
 on
+e
 s 
-which appear three times
+and twos.
 %0A   
@@ -2160,25 +2160,34 @@
    ones 
-&
 = 
+(~
 threes
+) & ones
 ;%0A      
@@ -2201,17 +2201,26 @@
 wos 
-&
 = 
+(~
 threes
+) & twos
 ;%0A  
@@ -2219,32 +2219,41 @@
 twos;%0A        %7D%0A
+        %0A
         return o

update single number ii solution