Single Lonely Number

#beginners #programming #javascript #interview

In a given array of numbers, one element will show up once and the others will each show up twice. Can you find the number that only appears once in O(n) linear time? Bonus points if you can do it in O(1) space as well.

Example

lonelyNumber([4, 4, 6, 1, 3, 1, 3]) // 6

lonelyNumber([3, 3, 9])// 9

Solution 1

function lonelyNumber(nums){
    const obj={}
    for(const num of nums){
        obj[num]= (obj[num]||0)+1
    }
    for(const num in obj){
        if(obj[num]===1) return num
    }
}

console.log(lonelyNumber([4, 4, 6, 1, 3, 1, 3])); // 6
console.log(lonelyNumber([3, 3, 9])); // 9

Solution 2

function lonelyNumber(numbers) {
  return numbers.reduce((x, y) => x ^ y, 0);
}

console.log(lonelyNumber([4, 4, 6, 1, 3, 1, 3])); // 6
console.log(lonelyNumber([3, 3, 9])); // 9