Find the element that appears once

As described here, Median of elements of an array can be found in worst-case O(n) time and O(1) extra-space. So we can solve the problem with divide-and-conquer method:

Find the median in O(n) time and count number of elements which are less than or equal to median in O(n). If this number is 3k+1, it means that answer is less than or equal to median, so omit the elements which are greater than median in O(n). Else, omit ones which are less than or equal to median. Then recursively find answer in remaining elements in T(n/2). Note: number of remaining elements is n/2 because we have omitted half of elements.

So T(n) = T(n/2)+O(n) = O(n) and we need O(1) extra space.

JavaScript solution:

function findElement(arr) {
  var ones = 0;
  var twos = 0;
  for (var i = 0; i < arr.length; i++) {
    ones = (ones ^ arr[i]) & ~twos;
    twos = (twos ^ arr[i]) & ~ones;
  }
  return ones;
}

If O(1) space constraint was not there, you could've gone for a hashmap with values being the count of occurrences.

int getUniqueElement(int[] arr)
{
    int ones = 0 ; //At any point of time, this variable holds XOR of all the elements which have appeared "only" once.
    int twos = 0 ; //At any point of time, this variable holds XOR of all the elements which have appeared "only" twice.
    int not_threes ;

    for( int x : arr )
    {
        twos |= ones & x ; //add it to twos if it exists in ones
        ones ^= x ; //if it exists in ones, remove it, otherwise, add it

        // Next 3 lines of code just converts the common 1's between "ones" and "twos" to zero.

        not_threes = ~(ones & twos) ;//if x is in ones and twos, dont add it to Threes.
        ones &= not_threes ;//remove x from ones
        twos &= not_threes ;//remove x from twos
    } 
    return ones;
}

Basically, it makes use of the fact that x^x = 0 and 0^x=x. So all paired elements get XOR'd and vanish leaving the lonely element.

In short :

If a bit is already in ones, add it to twos.

XOR will add this bit to ones if it's not there or remove this bit from ones if it's already there.

If a bit is in both ones and twos, remove it from ones and twos.

When finished, ones contains the bits that only appeared 3*n+1 times, which are the bits for the element that only appeared once.