Finding a Number which Appears Once in Array where All Other Numbers Appear Three Times

http://www.geeksforgeeks.org/find-the-element-that-appears-once/

Given an array where every element occurs three times, except one element which occurs only once. Find the element that occurs once. Expected time complexity is O(n) and O(1) extra space.
Examples:

Input: arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3}
Output: 2

int getSingle(int arr[], int n)

{

    // Initialize result

    int result = 0;

 

    int x, sum;

 

    // Iterate through every bit

    for (int i = 0; i < INT_SIZE; i++)

    {

      // Find sum of set bits at ith position in all

      // array elements

      sum = 0;

      x = (1 << i);

      for (int j=0; j< n; j++ )

      {

          if (arr[j] & x)

            sum++;

      }

 

      // The bits with sum not multiple of 3, are the

      // bits of element with single occurrence.

      if (sum % 3)

        result |= x;

    }

 

    return result;

}

http://gohired.in/2015/01/find-the-element-that-appears-once-others-appears-thrice/
1) Whenever we get element,   XOR’d to the variable “ones”.
2) Now if its repeated number it will be removed from “ones” and we xor it to “twice”.
3) A number appears twice will be removed from once, twice and stored in “thrice”
4) To remove all those are in common to “ones” and “twice” What we do is…
http://www.codinghelmet.com/?path=exercises/number-appearing-once-in-array-of-numbers-appearing-three-times
https://www.quora.com/Given-an-integer-array-such-that-every-element-occurs-3-times-except-one-element-which-occurs-only-once-how-do-I-find-that-single-element-in-O-1-space-and-O-n-time-complexity
Read full article from Finding a Number which Appears Once in Array where All Other Numbers Appear Three Times