[16 Feb 2020] Given an array where every element occurs three times, except one element which occurs only once.

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
In the given array all element appear three times except 2 which appears once.

Input: arr[] = {10, 20, 10, 30, 10, 30, 30}
Output: 20
In the given array all element appear three times except 20 which appears once.

Following is another O(n) time complexity and O(1) extra space method suggested by aj. We can sum the bits in same positions for all the numbers and take modulo with 3. The bits for which sum is not multiple of 3, are the bits of number with single occurrence.
Let us consider the example array {5, 5, 5, 8}. The 101, 101, 101, 1000
Sum of first bits%3 = (1 + 1 + 1 + 0)%3 = 0;
Sum of second bits%3 = (0 + 0 + 0 + 0)%0 = 0;
Sum of third bits%3 = (1 + 1 + 1 + 0)%3 = 0;
Sum of fourth bits%3 = (1)%3 = 1;
Hence number which appears once is 1000

Below is the implementation of above approach:

// C++ program to find the element
// that occur only once
#include <bits/stdc++.h>
using namespace std;
#define INT_SIZE 32

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;
}

// Driver code
int main()
{
    int arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The element with single occurrence is " << getSingle(arr, n);
    return 0;
}
Output :
The element with single occurrence is 7

// Java code to find the element
// that occur only once

class GFG
{
    static final int INT_SIZE = 32;
   
    // Method to find the element that occur only once
    static int getSingle(int arr[], int n)
    {
        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) == 0)
                sum++;
            }
            // The bits with sum not multiple of 3, are the
            // bits of element with single occurrence.
            if ((sum % 3) == 0)
            result |= x;
        }
        return result;
    }
   
    // Driver method
    public static void main(String args[])
    {
        int arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7};
        int n = arr.length;
        System.out.println("The element with single occurrence is " + getSingle(arr, n));
    }
   
}

# Python3 code to find the element
# that occur only once
INT_SIZE = 32

def getSingle(arr, n) :
   
    # Initialize result
    result = 0
   
    # Iterate through every bit
    for i in range(0, INT_SIZE) :
       
        # Find sum of set bits
        # at ith position in all
        # array elements
        sm = 0
        x = (1 << i)
        for j in range(0, n) :
            if (arr[j] & x) :
                sm = sm + 1
               
        # The bits with sum not
        # multiple of 3, are the
        # bits of element with
        # single occurrence.
        if (sm % 3) :
            result = result | x
   
    return result
   
# Driver program
arr = [12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7]
n = len(arr)
print("The element with single occurrence is "
      ,getSingle(arr, n))