Description
Given an 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?
Solution
Bit-manipulation, time O(n), space O(1)
class Solution {
public int singleNumber(int[] nums) {
int single = 0;
for (int i = 0; i < 32; ++i) {
int sum = 0;
for (int n : nums) {
sum += (n >> i) & 1;
}
sum %= 3;
single |= sum << i;
}
return single;
}
}
