136. Single Number.md

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.

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

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.

2. Solutions

Solution 1: Language: C Bitwise Operations

We have XOR bitwise operations as following $$ \begin{equation} \begin{split} 0 \oplus 0 = 0 \ 0 \oplus 1 = 1 \ 1 \oplus 0 = 1 \ 1 \oplus 1 = 0 \end{split} \end{equation} $$ and for example $3 \oplus 3 \oplus 4 \oplus 4 \oplus 5 = 5$.

• Wednesday, 28 October, 2020
• Time Complexity: $O(n)$
• Space Complexity: $O(1)$
• Runtime: 12 ms, faster than 99.15% of C online submissions for Single Number.
• Memory Usage: 7.4 MB, less than 32.15% of C online submissions for Single Number.

int singleNumber(int *nums, int numsSize) {
    int single = 0;
    for (int i = 0; i < numsSize; i++) {
        single ^= nums[i];
    }
    return single;
}