SimuVedaAlgorithms Lab Open in the lab

Bit manipulation / Beginner

Single Number with XOR Visualizer

XOR is 1 where two bits differ. x ^ x = 0 and x ^ 0 = x, and the order does not matter. So XOR everything: each pair cancels itself, and only the single value is left.

Start the Single Number with XOR simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n)
Average timeO(n)
Worst timeO(n)
Extra spaceO(1)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. acc starts at 0.
  2. Value 1: x = 4. XOR flips every bit of acc where x has a 1.
  3. acc is now 4.
  4. Value 2: x = 1. XOR flips every bit of acc where x has a 1.
  5. acc is now 5.
  6. Value 3: x = 2. XOR flips every bit of acc where x has a 1.
  7. acc is now 7.
  8. Value 4: x = 1. XOR flips every bit of acc where x has a 1.
  9. acc is now 6.
  10. Value 5: x = 2. XOR flips every bit of acc where x has a 1.
  11. acc is now 4.
  12. Every pair cancelled out. The value that appears once is 4.

Try it with your own input →

Single number with XOR in Java, Python, C++, C and JavaScript

int singleNumber(int[] nums) {
  int acc = 0;
  for (int x : nums) {
    acc ^= x;
  }
  return acc;
}
def single_number(nums):
    acc = 0
    for x in nums:
        acc ^= x
    return acc
int singleNumber(const vector<int>& nums) {
  int acc = 0;
  for (int x : nums) {
    acc ^= x;
  }
  return acc;
}
int singleNumber(int nums[], int n) {
  int acc = 0;
  for (int i = 0; i < n; i++) {
    acc ^= nums[i];
  }
  return acc;
}
function singleNumber(nums) {
  let acc = 0;
  for (const x of nums) {
    acc ^= x;
  }
  return acc;
}

In an interview

LeetCode 136, Single Number. Related: 268 Missing Number, 137 Single Number II, 260 Single Number III.

A HashSet works in O(n) space; sorting works in O(n log n). XOR does it in one pass and O(1) space, which is the answer interviewers are looking for.

More bit manipulation