# 136. Single Number

## The Problem

Link to original problem on Leetcode

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

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

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


Example 2:

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


## My Solution

This solution avoids creating anything new in memory, such as another list or hash map to keep track. I don't really want to track numbers--just find the unique one. To make it easier to do this in a single loop over the existing array, I sort it. Then I can just compare each number to its neighbors and return whichever one doesn't have a matching neighbor.

Time complexity of O(N) for my operation not counting the sort. I think space complexity is O(1), since I created nothing new. Not sure how the sort might affect that, however.

var singleNumber = function(nums) {    // First sort the numbers so I can loop through only once    // without creating another array or hashmap    nums.sort();    // Once sorted, if the first two don't match, the first number    // must be the unique one. (The second would have a pair in    // third position.)    if (nums[0] !== nums[1]) {        return nums[0];    }    // Loop through sorted nums starting at index 1 and ending at length - 1.    // We already checked index 0.    for (let i = 1, j = nums.length - 1; i < j; i++) {        // If nums[i] doesn't equal either of its neighbors, it is unique.        if (nums[i - 1] !== nums[i] && nums[i] !== nums[i+1]) {            return nums[i];        }    }    // If you get this far, the final number must be unique.    return nums[nums.length - 1];};

## Best Solution

Use bitwise operations. The XOR of number n and 0 is n. Therefore, n XOR n is 0.

If you XOR each number in the array together, all the duplicates cancel out.

Time complexity of O(N) and space complexity of O(1).

var singleNumber = function(nums) {
return nums.reduce((result, num) => result ^ num)
};