# [leetcode] Single Number II

### 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?

This is an extremely tricky problem.

First, we consider each bit of the 32bits integer.

Each bit can be either 1 or 0. Let’s consider bit as an example. other bits(bit[31~1]) are similar to bit.

Since every integer appears three times except for one, 1 and 0 also appears in multiples times of three or with one over. If the count of 1 can be divided by 3, the bit 0 of the single appearance number is 0.

If the count of 1 can be divided by 3 with one over, the bit 0 of the single appearance number is 1.

```class Solution {
public:
int singleNumber(vector<int>& nums) {
int digits; // digits lowest digit, digits highest digit
int re = 0;
memset(digits, 0, sizeof(digits));
for(auto it = nums.begin(); it != nums.end(); it++){
for(size_t i = 0; i < 32; i++){
digits[i] = (digits[i] + (((*it) >> i) & 0x00000001)) % 3;
}
}
for(int i = 31; i >= 0; i--){//i should be declared as int, not size_t.
re = (re << 1) + digits[i];
}
return re;
}
};``` This site uses Akismet to reduce spam. Learn how your comment data is processed.