Single Number


Solution

  • Problem requires to write algorithm that runs in linear time with constant space usage. Before solving the issue I got to learn about bitwise operators. They are not widely used in daily web development, but definetely having them in toolkit would not hurt.
  • When using ^ (XOR) operator when get 1 if bits are different. If same numbers are encountered when looping through the array they would cancel each other leaving us the uninqe number.
function singleNumber(nums: number[]): number {
    let result = nums[0]
    for(let i = 1; i < nums.length; i++){
        result = nums[i] ^ result
    }

    return result
};

Performance

  • Runtime - O(n) (beats 77%)
  • Memory - O(1) beats 72%