Single Number III

Leetcode Problem 260: Single Number III

Problem Summary

Given an integer array where every element appears exactly twice except for exactly two elements that each appear only once, find and return those two unique elements in any order.

Your solution must run in linear time and use only constant extra space.

Constraints:

• The array has between 2 and 30,000 elements.
• Each element is a 32-bit signed integer.
• Exactly two elements appear once; all others appear exactly twice.

Techniques

• Array
• Bit Manipulation

Solution

// I was going to loop to get the first bit difference but then I found this beautiful solution that leverages 
// the xor property and the two complements representation.
function singleNumber3(nums: number[]): number[] {
    let singleXorOtherSingle = nums.reduce((result, current) => result ^ current, 0)
    let bitDifference = singleXorOtherSingle & -singleXorOtherSingle
    let singleGroup = nums.filter(it => it & bitDifference)
    let otherSingleGroup = nums.filter(it => !(it & bitDifference))

    return [
        singleGroup.reduce((result, current) => result ^ current, 0),
        otherSingleGroup.reduce((result, current) => result ^ current, 0)
    ]
}

console.log(singleNumber3([1, 2, 1, 3, 2, 5]))