Single Number — XOR Bit Trick O(n) Time O(1) Space [Meta Classic]
Sanjeev SharmaAdvertisement
Problem Statement
Given a non-empty array of integers where every element appears twice except for one — find that one.
Constraints: Linear time, constant space.
Example:
Input: [4, 1, 2, 1, 2] → 4
Input: [2, 2, 1] → 1
- Intuition — XOR Magic
- Solutions in All 5 Languages
- C
- C++
- Java
- JavaScript
- Python
- Complexity: O(n) time, O(1) space
- Single Number II — Every element appears 3 times except one
- Single Number III — Two elements appear once
Intuition — XOR Magic
XOR has two key properties:
a ^ a = 0(any number XOR itself is 0)a ^ 0 = a(any number XOR 0 is itself)- XOR is commutative and associative
So: a ^ b ^ a = b ^ (a ^ a) = b ^ 0 = b
XOR all elements together → all pairs cancel → only the unique element remains.
result = 0
for each num in nums:
result ^= num
return result
Solutions in All 5 Languages
C
int singleNumber(int* nums, int numsSize) {
int result = 0;
for (int i = 0; i < numsSize; i++) {
result ^= nums[i];
}
return result;
}
C++
#include <vector>
#include <numeric>
using namespace std;
class Solution {
public:
int singleNumber(vector<int>& nums) {
int result = 0;
for (int num : nums) result ^= num;
return result;
// One-liner: return reduce(nums.begin(), nums.end(), 0, bit_xor<int>());
}
};
Java
class Solution {
public int singleNumber(int[] nums) {
int result = 0;
for (int num : nums) result ^= num;
return result;
}
}
JavaScript
function singleNumber(nums) {
return nums.reduce((acc, num) => acc ^ num, 0);
}
Python
from typing import List
from functools import reduce
from operator import xor
class Solution:
def singleNumber(self, nums: List[int]) -> int:
return reduce(xor, nums)
# Or: result = 0; [result := result ^ n for n in nums]; return result
Complexity: O(n) time, O(1) space
Single Number II — Every element appears 3 times except one
Use 3-state bit counters (ones, twos):
def singleNumberII(nums):
ones = twos = 0
for num in nums:
ones = (ones ^ num) & ~twos
twos = (twos ^ num) & ~ones
return ones
Single Number III — Two elements appear once
def singleNumberIII(nums):
xor = 0
for n in nums: xor ^= n # xor = a ^ b
diff_bit = xor & (-xor) # rightmost differing bit
a = 0
for n in nums:
if n & diff_bit: a ^= n # group by this bit
return [a, xor ^ a]
Advertisement
