136. Single Number

1. Description

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

2. Follow Up

Could you implement a solution with a linear runtime complexity and without using extra memory?

3. 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

4. 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.

5. Solutions

Bit Operations (Follow Up)

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

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

        return single;
    }
};