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

Try this Problem on your own or check similar problems:

1. Missing Number
2. Single Number II
3. Find the Duplicate Number

Solution:

public int singleNumber(int[] nums) {
    int res = 0;
    for(int num: nums){
        res ^= num;
    }
    return res;
}

Time/Space Complexity:

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

Explanation:

As in Missing Number the brute-force is trivial loop over range 1..n and check if the element exists in auxiliary (helper) data structure (for example set), if not just place it in the resulting array. However we can use the XOR operator (you can find detailed description in Missing Number ), since all numbers in pair will eliminate each other (x^x=0) and the only number remaining will be the number appearing only once in the input array.