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)