Single Number

Problem

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.

Constraints

• 1 <= nums.length <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• Each element in the array appears twice except for one element which appears only once.

Solution

The problem Single Number can be solved using an XOR bitwise operator. Every element that appears twice in the array will offset each other and the single element which appears only once will be XORed with 0 resulting in that very element.

Implementation

class Solution
{
  public:
    int singleNumber(vector<int> &nums)
    {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);

        int ret = 0;
        for (int num : nums)
            ret ^= num;

        return ret;
    }
};