/*
*
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?
*/
#include <iostream>
#include <vector>
using namespace std; 
class Solution {
public:
    int singleNumber(int A[], int n) {
    	
    	int i = 0;
    	int j = 0;
    	int bit[32] = {0};
    	int singleOne = 0;
    	for(i = 0; i < 32; i++){
    		for(j = 0; j < n; j++){
    			bit[i] = bit[i] + ((A[j] >> i) & 1);
    		}
			singleOne = singleOne | ((bit[i] % 3) << i);
    	}
    	
    	
        return singleOne;
    }
};

int main(){
	Solution solution;
	int array[10] = {-3, -3, -3, -120, -120, -120, 36, 36, 36, -4};	
	cout<<solution.singleNumber(array, 10)<<endl;
	return 1;
}

leetcode Single Number II