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?

 

Have you been asked this question in an interview? 

/**We can use the bit operation to do this problem*If you have a problem to understand the bit operation,*then you can think | , & , ^, ~ as the set operation union, intersection and symmetric difference and set complement respectively.*/public class Solution {    public int singleNumber(int[] A) {        int once = 0;        int twice = 0;        int triple = 0;        for(int i = 0 ; i < A.length ; i++){            //update twice when A[i] is added. if A[i] is in once, then added it to twice,            //otherwise, twice is not needed to updated                 twice |= A[i] & once;           //update once            once = A[i] ^ once;           //triple is exactly the intersection of once and twice            triple = once&twice;           //update once and twice again(remove all integer in triple)             once ^= triple;            twice ^= triple;        }        //return the integer in once or twice        return once | twice;    }}