LeetCode Solutions
260. Single Number III
Time: $O(n)$ Space: $O(1)$
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
const int xors = accumulate(begin(nums), end(nums), 0, bit_xor<>());
const int lowbit = xors & -xors;
vector<int> ans(2);
// Seperate nums into two groups by the lowbit
for (const int num : nums)
if (num & lowbit)
ans[0] ^= num;
else
ans[1] ^= num;
return ans;
}
};
class Solution {
public int[] singleNumber(int[] nums) {
final int xors = Arrays.stream(nums).reduce((a, b) -> a ^ b).getAsInt();
final int lowbit = xors & -xors;
int[] ans = new int[2];
// Seperate nums into two groups by the lowbit
for (final int num : nums)
if ((num & lowbit) > 0)
ans[0] ^= num;
else
ans[1] ^= num;
return ans;
}
}
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
xors = functools.reduce(operator.xor, nums)
lowbit = xors & -xors
ans = [0, 0]
# Seperate nums into two groups by the lowbit
for num in nums:
if num & lowbit:
ans[0] ^= num
else:
ans[1] ^= num
return ans