[Leetcode] Single Number II

Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.

Analysis: 
One linear solution is to count total sum of each bit for all elements, and divide that by 3,  as every element appear three times except one,  the remaining bit is honored by the integer appeared only once.

Solution:

    int singleNumber(int A[], int n) {
       int result = 0;
       int i;
       int x;
       int sum;
       int size = 8 * sizeof(int);
    
       // Walk through every bit
       for (i = 0; i <size ; i++)
       {
          sum = 0;       // reset sum for current bits
          
          x = (1<<i);     
          for (int j=0; j< n; j++ )   
          {
             if (A[j] & x)  //  ith bit is set for A[j], add it to the sum
                 sum++;
          }
          if (sum % 3)  // append the remaining bit to result using OR operation
          result |= x;
      
       }

       return result;
        
    }