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.
Recommended Time and Space Complexity
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)