Leet Code Daily 2024-05-31 - Single Number III
Solution
Let's say and are the numbers we are looking for.
We know:
There is at least one bit diffecnce between and . If we split numbers into two buckets by that bit and perform, and will be put into diffrent buckets.
And then we can just perform XOR sum again.
Code
class Solution {
public:
int computeXOR(vector<int>& nums) {
int ret = 0;
for (const auto& x : nums) {
ret = ret ^ x;
}
return ret;
}
vector<int> singleNumber(vector<int>& nums) {
int t = computeXOR(nums);
vector<int> buckets[2];
for (int mask = 1;; mask <<= 1) {
if (mask & t) {
for (const auto& x : nums) {
buckets[(mask & x) ? 1 : 0].push_back(x);
}
break;
}
}
return vector<int>{computeXOR(buckets[0]), computeXOR(buckets[1])};
}
};