Single Number III — XOR Partition
Sanjeev SharmaAdvertisement
Problem
Exactly two numbers appear once; all others appear twice. Find both.
Approach — XOR then Partition
- XOR all →
xor = a ^ b(non-zero since a != b) - Find any set bit of xor (use
xor & (-xor)) - Partition numbers into two groups by that bit; XOR each group → gets a and b
Time: O(n) | Space: O(1)
Solutions
Python
class Solution:
def singleNumber(self, nums: list[int]) -> list[int]:
xor=0
for n in nums: xor^=n
bit=xor&(-xor) # isolate rightmost set bit
a=b=0
for n in nums:
if n&bit: a^=n
else: b^=n
return [a,b]
C++
class Solution {
public:
vector<int> singleNumber(vector<int>& nums){
int xr=0; for(int n:nums) xr^=n;
int bit=xr&(-xr); int a=0,b=0;
for(int n:nums){if(n&bit)a^=n;else b^=n;}
return {a,b};
}
};
Complexity
- Time: O(n) | Space: O(1)
Advertisement
