Single Number

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

So if you're given an array: [2,1,5,3,1,5,2] the result will be 3 since 3 occurs once.

So let's go through the thinking process from brute force to an optimized version.

1: Brute force: O(n^2) time.

The natural way of solving this problem would be to go over each and every element and check whether the same element appears again, if it doesn't then that's our answer. Based on that thinking the solution would be:

var singleNum = function(nums){
    for(let i=0;i<nums.length;i++){
        let flag = true;
        for(let j=i+1;i<nums.length;j++){
                if(nums[i] == nums[j]){
                   flag = false;
                  }
        }
        if(flag == true) return nums[i];
     }
     return -1;
}

2: Sorting O(nlogn) time:

As you might've guessed it, we can be a bit smarter here, we can sort the array in O(nlogn) time, compare if two consecutive elements are equal and find the element.

var singleNum = function(nums){
    nums.sort((a,b)=>a-b);
    for(let i=0;i<nums.length-1;i++){
        if(nums[i] != nums[i+1]) return nums[i];
     }
     return -1;
}

3: HashMap O(n) time and O(n) space.

As you might know, HashMap gives us access to elements in O(1) time, so we'll take advantage of it. We will create a HashMap, as we parse through the array, we shall keep the entries of it in our HashMap when we come across an element for the first time, we shall store the entry as {element: true}, if we come across the element again, we shall flip the flag ie {element:false}. So based on this :

var singleNum = function(nums){
    let map = {}
    for(let i=0;i<nums.length-1;i++){
        if(map[nums[i]]) map[nums[i]] = false;
        else map[nums[i]] = true;
     }
     for(let [key, value] of Object.entries(map)){
         if(value) return key;
     }
     return -1;
}

This is good but we're taking up extra memory, ie space, and as you might've experienced from you're ex, you should always give space, in this can we solve this in O(1) space and O(n) time? let's see how.

4: Bit Manipulation O(n) time and O(1) space.

We're given that each number occurs twice except 1 number, so we've to find a way that will negate out elements which were already existing while keeping track of that unique element.

XOR concept:

If we take XOR of zero and some bit, it will return that bit
a ⊕ 0 = a
If we take XOR of two same bits, it will return 0
a ⊕ a = 0
So for elements [a,a,b]
a ⊕ b ⊕ a = a ⊕ a ⊕ b = (a ⊕ a ) ⊕ b = 0 ⊕ b = b

based on this approach:

var singleNum = function(nums){
    let res = 0;
    for(let i=0;i<nums.length-1;i++){
        res  = res ^ nums[i];
     }
     return res;
}

Now you know how to find a unique element in a bunch of duplicate elements.
It's sometimes amazing to see how we can optimize even simple problems.

github: https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/singleNumber.js