Back to solutions

Single Number

EasyBit Manipulation

Every element appears twice except for one. Find that single element in linear time and constant space.

Open problem
Constraints
  • 1 <= n <= 3 * 10^4
  • Each element appears twice except one

XOR accumulation

Time O(n)Space O(1)

XOR is associative and a^a = 0. XOR-ing all numbers cancels the duplicates and leaves the unique value.

#include <bits/stdc++.h>
using namespace std;

int singleNumber(vector<int>& nums) {
    int x = 0;
    for (int v : nums) x ^= v;
    return x;
}