JuniorCodeVery commonNot answered yet
Find the unique element in an array where all others appear twice
In an integer array every element appears exactly twice except one. Return that single unique element.
Requirements:
- O(n) time, O(1) extra space, a single pass — no hash map and no sorting.
- Do not modify the input array.
int findUnique(const std::vector<int>& nums) {
// your code here
}Write the implementation.
XOR all elements together. Pairs cancel out (a XOR a = 0), so the result is the single element that has no pair. Time O(n), space O(1), single pass.
- ✗Using a hash map — O(n) space is unnecessary when XOR gives O(1)
- ✗Sorting the array — O(n log n) and modifies input
- ✗Not generalising: this only works when exactly one element appears an odd number of times
- →How would you find two unique elements when all others appear twice?
- →How would you find the unique element when all others appear three times?
Contents
Task
In an integer array, every element appears exactly twice except for one. Find that one in O(n) time and O(1) space.
Solution
int findUnique(const std::vector<int>& nums) {
int result = 0;
for (int x : nums) result ^= x;
return result;
}Key points
a XOR a = 0anda XOR 0 = a— the two key properties.- Order does not matter — XOR is commutative and associative.
- Single pass, no extra memory.
Contents
