Single Number — XOR Cancellation

Problem

Every element appears twice except one. Find that element.

Example: [4,1,2,1,2] → 4

Approach — XOR All Elements

a ^ a = 0 and 0 ^ b = b. XOR everything → only the single number remains.

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

Solutions

C

int singleNumber(int* nums, int n) {
    int res=0;
    for(int i=0;i<n;i++) res^=nums[i];
    return res;
}

C++

class Solution {
public:
    int singleNumber(vector<int>& nums){
        int res=0; for(int n:nums) res^=n; return res;
    }
};

Java

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

JavaScript

var singleNumber = n => n.reduce((a,b)=>a^b,0);

Python

from functools import reduce
from operator import xor
class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        return reduce(xor, nums)

Complexity

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