Single Number — Leetcode

Topic: Array
Difficulty: Easy
Question Number: 136

Problem Statement:
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,1]
Output: 1

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4

Explanation:
This question can be solved using HashSet or pointers but using the XOR concept can hep to optimize code in better way.

Concept

• XOR of zero and some bit returns that bit
  a⁰ = a
• XOR of two same bits returns 0
  a^a = 0
• XOR of a^b^a for some bits a and b returns b
  a^b^a = (a^a)^b = 0^b = b

So we can XOR all bits together to find the unique number.

Code:

class Solution {
    public int singleNumber(int[] nums) {
        int mask = 0;

        for(int num : nums) {
            mask ^= num;
        }

        return mask;
    }
}

Thank you
Oshi Raghav