Single Number

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 O(n) time complexity and O(1) extra space complexity.

Examples

Example 1:

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

Example 2:

Input: nums = [4, 1, 2, 1, 2]
Output: 4
Explanation: 1 and 2 each appear twice, so 4 is the single number.

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 exactly twice except for one element which appears exactly once.

Expected Complexity

• Time: O(n)
• Space: O(1)