Single Number
Problem Description
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.
Example 1:
Example 2:
Example 3:
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.
Solve it on LeetCode
Approaches
1. Brute Force
Intuition:
In a brute force approach, for each element in the array, we can check if it appears again in the array. We can do this by comparing each element against all others. The element that doesn't have a duplicate is the single number.
Code:
- Time Complexity: O(n^2), due to nested loops
- Space Complexity: O(1)
2. HashMap
Intuition:
Utilize a HashMap to count the occurrences of each element. Then, iterate over the HashMap to find the element with a count of one, which is our single number.
Code:
- Time Complexity: O(n),
- Space Complexity: O(n), due to hash map
3. Bit Manipulation
Intuition:
The most optimal solution involves using the XOR operation.
XOR has three important properties:
- x ⊕ x = 0: A number XOR'ed with itself cancels out.
- x ⊕ 0 = x: XOR with zero leaves the number unchanged.
- XOR is commutative and associative: (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)
Putting these together:
When we XOR all elements in the array, every duplicate pair cancels out to 0, and only the unique element survives.
- Time Complexity: O(n)
- Space Complexity: O(1)