# 137. Single Number II (Medium)

https://leetcode.com/problems/single-number-ii/

Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

```Input: [2,2,3,2]
Output: 3
```

Example 2:

```Input: [0,1,0,1,0,1,99]
Output: 99```

## Solutions

### 1.

``````class Solution {

// Assume we sum up all nums bit by bit, we adopt 32 counter to count
// 1s on each bit. Since all the numbers appear thrice except one, for a specific bit,
// we can always mod 3 to get 1 if the special number carries 1 on that bit; in a similar way
// we can sort all the 0s on this special number.

public int singleNumber(int[] nums) {
int ans = 0;

for (int i = 0; i < 32; i++) {
int k = 1 << i;

int count = 0;
for (int j = 0; j < nums.length; j++) {
// can not use (nums[j] & k) > 0, there may be negative values
if ((nums[j] & k) != 0) {
count++;
}
}

ans += k * (count % 3);
}

return ans;
}
}
``````

### 2.

``````class Solution {

// This solution is hacky. Memorize it or ignore it.

public int singleNumber(int[] A) {
int ones = 0;
int twos = 0;
for (int i = 0; i < A.length; i++) {
ones = (ones ^ A[i]) & ~twos;
twos = (twos ^ A[i]) & ~ones;
}

return ones;
}
}
``````