Find the Element That Appears Once

easy bit manipulation xor

Problem

Every value in the array appears exactly twice except for one. Find the loner. Use the XOR identity x ⊕ x = 0: XOR-ing every element together cancels each duplicated pair, and the lone value remains.

Inputnums = [4, 2, 9, 4, 2]

Output9

4 ⊕ 2 ⊕ 9 ⊕ 4 ⊕ 2 = 9.

nums (every value paired except one)

def single_number(nums):
    acc = 0
    for x in nums:
        acc ^= x
    return acc

function singleNumber(nums) {
  let acc = 0;
  for (const x of nums) acc ^= x;
  return acc;
}

class Solution {
    public int singleNumber(int[] nums) {
        int acc = 0;
        for (int x : nums) acc ^= x;
        return acc;
    }
}

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

Time: O(n) Space: O(1)