Solution & Explanation: Leetcode 30 Day Challenge Day 1 - Single Number

#leetcode #computerscience #algorithms #javascript

Challenge

https://leetcode.com/explore/featured/card/30-day-leetcoding-challenge/

Question

https://leetcode.com/problems/single-number/

Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
function singleNumber(nums) {
    const num = nums[0]
    for (let i = 1; i < nums.length; i++) {
        num ^= nums[i]  
    }
    return num
};

Explanation

This solution uses the properties of the XOR operation to find the number by XOR'ing all of them together. With XOR the rule is that the result is 1 if the numbers are different and 0 if they’re the same. The XOR operator is ^.

Example:

1 ^ 1 = 0 (same 1s, leads to 0)
0 ^ 0 = 0 (same 0s, leads to 0)
1 ^ 0 = 1 (different 1 and 0 leads to 1)
0 ^ 1 = 1 (different 1 and 0 leads to 1)

Since XOR operates on the binary representation of a number, you can see the effect of doing XOR on two 2s will result in 0.

2 in binary is 010

2 ^ 2 is the same as 010 ^ 010.

If we lay it out like a multiplication problem its easier to see how the bits align. The form is similar to multiplication, addition, subtraction..etc except the operation is XOR. Similar concept, but different operation.

Example:

2 + 2 = 4 is equivalent to

2 +
2
—
4

2 ^ 2 is equivalent to
010 ^
010
——
?

Where ? Is the answer. If we work through this problem by looking at the top and bottom numbers from right to left (just like multiplication, addition, subtraction..etc) we get 000:

0 ^ 0 = 0
1 ^ 1 = 0
0 ^ 0 = 0

Since the top and bottom are the same number, each position will contain the same bit (0 or 1), we get 0 based on the rule mentioned above “0 if they’re the same”. Because of this, we get 0 if we XOR any number by itself. Another example is 4 ^ 4

100 ^
100
——
?

0^0=0
0^0=0
1^1=0

Each time you XOR a number with itself, it “zeroes out” the number. When working with decimals this happens under the hood too. The trick for this question is realizing that this “zeroing” out will happen even if you XOR another number beforehand. For example:

2 ^ 1 ^ 2 = 1 because the 2 ^ 2 “zero” each other out

010 ^
001 ^
010
——
?

0^1 = 1, 1 ^ 0 = 1
1^0 = 1, 1 ^ 1 = 0
0^0 = 0, 0^0 = 0

010
001
010
——
001 <— only the 1 remains because the 2s (010) canceled each other out after the XOR

With this in mind you can see how you can identify a single missing number because all other pairs of numbers will “zero” each other out, just as they did in the 2 ^ 1 ^ 2 example.

7 ^ 3 ^ 9 ^ 3 ^ 7 ^ 4 ^ 4 = 9 because the 7s, 3s, and 4s zero each other out.