LeetCode: Single Number II

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?

---

We can solve this in bit level. Each integer is also a bit array of size 32. We can count the number of 1 occurred in each bit. If its 4 or 1, then the bit of the single number is also 1. Otherwise it is 0.

C++ Code:

/*
 * func: single_number
 * goal: find the single number in an array that occurs once
 * @param A: input array A
 * @param n: size of the array
 * return: the single number
 */
int singleNumber(int A[], int n) {
    vector<int> tmp;
    for(int i = 0; i < 32; ++i){
        int bit_count = 0;
        int curr_bit = 1 << i;
        for(int j = 0; j < n; j++){
            if(A[j] & curr_bit)
                ++bit_count;
        }
        (bit_count % 3) ? tmp.emplace_back(1) : tmp.emplace_back(0);
    }
    int num = 1;
    int result = 0;
    for(const int &digit : tmp){
        if(digit){
            result += num;
        }
        num <<= 1;
    }
    return result;
}

Python Code:

# func: find the single number in a list
# @param A: input list
# @return: single number
def single_numer(A):
    if not A:
        return 0
    digits = []
    for i in xrange(32):
        curr = 1 << i
        digit_count = 0
        for num in A:
            if num & curr:
                digit_count += 1
        if digit_count % 3:
            digits.append(1)
        else:
            digits.append(0)

    result = 0
    bit_helper = 1
    for digit in digits:
        if digit == 1:
            result += bit_helper
        bit_helper <<= 1

    if digits[-1] == 1:
        return result - (1 << 32)
    else:
        return result