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

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(arr) {

// SOLUTION I 

    const count = arr.reduce((obj, curr)=>{
        if(obj[curr] == undefined)
           obj[curr] = 1
         else
         obj[curr]++

        return obj
    }, {})


     for(const[key, value] of Object.entries(count)){
        if(value === 1){
         return key;
         }
     }

// SOLUTION II

     let res = 0, i, n = arr.length;
     for (i = 0; i < n; i++)
        res ^= arr[i];
        return res;

// SOLUTION III

    return arr.reduce((prev, curr) => prev^curr)
}

Let's say we have an input array arr of length n:

arr = [2, 3, 2, 4, 3]
n = 5

Solution I:

Here's a visualization of the count object after the reduce function is applied to the input array:

count = {
    2: 2,
    3: 2,
    4: 1
}

The for...of loop iterates over the count object and returns the first number with a count of 1. In this case, it returns 4.

Solution II:

This solution uses the bitwise XOR operator (^) to find the unique number in the array.

Here's a visualization of the XOR operation for the input array:

2 ^ 3 ^ 2 ^ 4 ^ 3 = 4

The XOR operator works by comparing the bits of each number in the array. If the bits match, the result is 0. If the bits don't match, the result is 1. In this case, 2 and 3 appear twice in the array, so their bits cancel out. The only number left with non-matching bits is 4.

Solution III:

This solution uses the reduce function and the XOR operator to find the unique number in the array.

Here's a visualization of the reduce function and the XOR operation for the input array:

[2, 3, 2, 4, 3].reduce((prev, curr) => prev^curr)
=> 2^3^2^4^3
=> 2^2^3^3^4
=> 0^0^4
=> 4

As you can see, the XOR operator cancels out the matching numbers, leaving only the unique number in the end.