136. Single Number

1. Description

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.

2. Example

Example 1

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

Example 2

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

Example 3

Input: nums = [1]
Output: 1

3. Constraints

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

4. Solutions

Bit Operations

n = nums.size()
Time complexity: O(n)
Space complexity: O(1)

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

        return unique_num;
    }
};