Single Number I (LeetCode)

Single Number I

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^link.

Example 1:
  Input: nums = [2,2,1]
  Output: 1

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

Example 3:
  Input: nums = [1]
  Output: 1

Solution

We will discuss two approaches for this problem. The first one will be kind of naive way of solving the problem while the second goes a bit more elegant 🧠. Let’s go! 🚀

Approach 1. A simple way of solving this problem could just be using dictionary to store the count of every number in the given array and return the element which appeared once. In order to achieve this, we shall initialize a new dictionary whose keys are elements of the given array and values set to 0:

count = {num: 0 for num in nums}

Then, we iterate of the array nums and increment the value at the corresponding key:

for i in nums:
    count[i] += 1

Finally, we find the key whose value in count is 1 and return this key:

for key in count.keys():
    if count[key] == 1:
        return key

Our final code should look like so:

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        count = {num: 0 for num in nums}
        for i in nums:
            count[i] += 1
        for key in count.keys():
            if count[key] == 1:
                return key

• Memory: In this approach, we used an extra memory to store the frequency of each element which is $O(n)$ ($n$ - the length of nums)
• Runtime: We iterated through nums and count, which is $O(n)$ as well.

Approach 2. We could improve this solution to use only constant extra space while keeping the same runtime complexity!

It’s time to push back for a second, and revise what the Exclusive OR (XOR) was 🤔.

Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false).

^{(Basically, it’s like adding up numbers module $2$ 💡)}

Let’s break down the main properties that we will need.

1. XOR ($\oplus$) is commutative: $x \oplus y = y \oplus x$
2. XOR is associative: $x \oplus (y \oplus z) = (x \oplus y) \oplus z$
3. For any $x$, we have $x \oplus 0 = x$
4. For any $x$, we have $x \oplus x = 0$

Note 1. The proof of the abovementioned four properties easily follow from the definition:

Note 2. The notation $\oplus$ is the one used to mean XOR by most textbooks, so I did also stick with this. (See also Zhegalkin Polynomials)

So far so good! But why do we need these❓

Let’s take the second example input/output given on LeetCode: nums = [4,1,2,1,2]. Let’s investigate what the XOR of all elements of nums look like?

What else can we do?

💡 Remember that $\oplus$ was commutative and associative, so we can interchange the order and group the pairs of the same two elements. Then use 3^rd and 4^th properties to simplify!

💥 Boom! So, what we get as a result is the desired answer since every duplicate elements vanish with its pair when XORed (due to the 4^th property).

Finally, our solution will basically be

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = nums[0]
        for i in range(1, len(nums)):
            ans = ans ^ nums[i]
        return ans

or to satisfy “one-liner fans”:

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return reduce(lambda x, y: x ^ y, nums)

• Memory: Obviously, the amount of extra memory is constant, that is $O(1)$ (fulfills the problem statement).
• Runtime: $O(n)$ since we only iterate over nums once.