Single Number – 136

🔗LC136 🟢 Easy 🧩 Pattern – XOR, Hashmap

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

Input: nums = [2,2,1]

Output: 1

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

Output: 4
Code language: JavaScript (javascript)

Solution

Bitwise XOR operator ^ is the only way to solve this question, personally, I don’t think we use it daily in programming hence this is more of a puzzle.

When we XOR two numbers they cancel out i.e 2^2 = 0, therefore in any order 2^1^3^2^1 = 3.

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
    let result = nums[0];
    for (let i = 1; i < nums.length; i++) {
        result = result ^ nums[i];
    }
    return result;
};Code language: JavaScript (javascript)

Solution without XOR

function singleNumber(arr) {
  let singleNumber;
  const seen = new Set();
  for (let num of arr) {
    if (seen.has(num)) {
      // If the number is already seen, remove it
      seen.delete(num);
    } else {
      // If it's not seen in the set, add it
      seen.add(num);
    }
  }
  // Only the single numbers remains in set,
  // covert to array and return
  singleNumber = [...seen][0];
  return singleNumber;
}

const numbers = [5, 1, 3, 5, 4, 1, 3];
console.log(singleNumber(numbers)); // 4Code language: JavaScript (javascript)

Back to Top