Single Number

Problem Statement

You are given a non-empty array of integers nums. Every integer appears twice except for one.

Return the integer that appears only once.

You must implement a solution with O(n) runtime complexity and use only O(1) extra space.

Example 1:

Input: nums = [3,2,3]


Output: 2

Example 2:

Input: nums = [7,6,6,7,8]


Output: 8

Constraints:

  • 1 <= nums.length <= 10000
  • -10000 <= nums[i] <= 10000

You must implement a solution with O(n) runtime complexity and use only O(1) extra space.

You should aim for a solution with O(n) time and O(1) space, where n is the size of the input array.

Hint 1

A brute force solution would be to check every element against every other element in the array. This would be an O(n^2) solution. Can you think of a better way?

Hint 2

Is there a way to store the counts of each element? Consider what data structures could be used and their time/space complexities.

Hint 3

Can we use bitwise operations to solve this problem?

Solution

Brute Force

def single_number(nums: List[int]) -> int:
    for i in range(len(nums)):
        flag = True
        for j in range(len(nums)):
            if i != j and nums[i] == nums[j]:
                flag = False
                break
        if flag:
            return nums[i]

Time complexity: O(n^2) Space complexity: O(1)

Hash Set

def single_number(nums: List[int]) -> int:
    seen = set()
    for num in nums:
        if num in seen:
            seen.remove(num)
        else:
            seen.add(num)
    return list(seen)[0]

Time complexity: O(n) Space complexity: O(n)

Sorting

def single_number(nums: List[int]) -> int:
    nums.sort()
    i = 0
    while i < len(nums) - 1:
        if nums[i] == nums[i + 1]:
            i += 2
        else:
            return nums[i]
    return nums[i]

Time complexity: O(n log n) Space complexity: O(1)

Bit Manipulation

def single_number(nums: List[int]) -> int:
    res = 0
    for num in nums:
        res ^= num
    return res

Time complexity: O(n) Space complexity: O(1)