Single Number

Patrick Leaton
Published: March 6, 2021, 12:43 a.m.
Problem Description

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

Follow up: Could you implement a solution with a linear runtime complexity and without using extra memory?

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

 

Constraints:

  • 1 <= nums.length <= 3 * 104
  • -3 * 104 <= nums[i] <= 3 * 104
  • Each element in the array appears twice except for one element which appears only once.

 

Description taken from https://leetcode.com/problems/single-number/.

Problem Solution

#Optimal Solution
#O(N) Time, O(1) Space
class Solution(object):
    def singleNumber(self, nums: List[int]) -> int:
        single = 0
        for num in nums:
            single ^= num
        return single
 
 
#Second Solution
#O(N) Time, O(N) Space
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        seen = {}
        for num in nums:
            if num in seen:
                seen[num] +=1
            else:
                seen[num] = 1           
        for i in range(0, len(nums)):
            if seen[nums[i]] == 1:
                return nums[i]

 

Problem Explanation

Binary Solution

The optimal solution requires using an XOR gate.  This works because every element appears twice besides the one we're looking for which appears once.

If we observe this operation table:

x XOR x = 0 

x XOR 0 = x

Since x XOR x = 0, each number that appears twice will zero out, leaving 0 XOR x which will give us x, the single number,

Let's initialize our single integer as zero.

        single = 0

 

We can then iterate through each number in the nums array and XOR the number by the single integer.

        for num in nums:
            single ^= num

 

After the numbers that appear twice zero out, since x XOR 0 = x, we will have the number that appeared only once remaining.

We will then return that number.

        return single

Hashmap Solution

We can also solve this problem using a similar solution to the First Unique Character in a String problem, although it is not the optimal solution.

We will traverse the array once and count the frequency of each character within a hashmap.  We will then traverse it once more and when we find a number with the frequency of one, we will return the number.

Let's initialize a dictionary to count the number of times we have seen each number.

        seen = {}

 

For each number in the array, if we have already seen the number, then we will increment its frequency in our dictionary.  if not, we will initialize it there with a value of one.

        for num in nums:
            if num in seen:
                seen[num] +=1
            else:
                seen[num] = 1    

 

Once we have each number and a count of their occurrence in our dictionary, we will traverse the array once more and return the number with a single occurrence.

        for i in range(0, len(nums)):
            if seen[nums[i]] == 1:
                return nums[i]

 

Additional Notes

Another way to solve this is to return 2 * sum(set(nums)) - sum(nums).  This is because c = 2 * (a+b+c) - (a+a+b+b+c). 

This approach may not be as apparent as the other two.