137. Single Number II Leetcode Java

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?

Solution:

More general than previous problem.

Since the array contains only integer, we can use a counter to count the numbers of each bits(total 32 bits for integer). All those elements appears three times, the counts of each bits are able to divided by 3.  So the remainder of bit count will be the single number.

Time complexity:O(32*n)=O(n) constant space.

 public int singleNumber(int[] A) {  
    if(A==null || A.length==0) return 0;  
    int[] dig=new int[32];  
    for(int i=0;i<32;i++){  
      for(int j=0;j<A.length;j++){  
        dig[i]+=(A[j]>>i) & 1;  
      }  
    }  
    int res=0;  
    for(int i=0;i<32;i++){  
      dig[i]=dig[i]%3;  
      res+=(dig[i]<<i);  
    }  
    return res;  
   }