1. Single Number

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.

• XOR operation : 1/0 ^ 1/0 = 0, 1 ^ 0 = 1 n ^ 0 = n
• For duplicates we would end up with zero TC: O(n) SC: O(1)

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

Some other methods

• Use count hash map and check whose count is 1 TC: O(n) SC: O(n)
• Sort and check if adjacent element is equal to current element TC: O(nlog(n)) SC: O(1)

class Solution {
public:
    int singleNumber(vector<int>& nums) { 
       sort(nums.begin(),nums.end());
        for(int i=1;i<nums.size();i+=2)
        {
            if(nums[i]!=nums[i-1])
                return nums[i-1];
        }
        return nums[nums.size()-1];
    }
};

• Store unique elements in set then sum and multiply. Take sum of original array and subtract from set sum 2*set_sum - org_sum