EasyBlind75ArrayBit Manipulation
Single Number
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.
Examples
Input
nums = [2,2,1]
Output
1
1 is the single number.
Input
nums = [4,1,2,1,2]
Output
4
4 is the single number.
Constraints
- •
1 <= nums.length <= 3 * 10^4 - •
-3 * 10^4 <= nums[i] <= 3 * 10^4 - •
Each element in the array appears twice except for one element which appears only once.
Approaches
Count occurrences using a hash map.
CodeT: O(n) | S: O(n)
def single_number(nums):
count = {}
for num in nums:
count[num] = count.get(num, 0) + 1
for num, cnt in count.items():
if cnt == 1:
return numSort and check adjacent elements.
CodeT: O(n log n) | S: O(1)
def single_number(nums):
nums.sort()
i = 0
while i < len(nums) - 1:
if nums[i] != nums[i + 1]:
return nums[i]
i += 2
return nums[-1]XOR all elements. Duplicates cancel out, leaving the single number.
Diagram
nums = [4,1,2,1,2]
4 ^ 1 = 5
5 ^ 2 = 7
7 ^ 1 = 6
6 ^ 2 = 4
Result: 4
CodeT: O(n) | S: O(1)
def single_number(nums):
result = 0
for num in nums:
result ^= num
return resultComplexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Hash Map | O(n) | O(n) | Count occurrences using a hash map. |
| Sorting | O(n log n) | O(1) | Sort and check adjacent elements. |
| XOR | O(n) | O(1) | XOR all elements. Duplicates cancel out, leaving the single number. |
Hash Map
T: O(n)S: O(n)
Count occurrences using a hash map.
Sorting
T: O(n log n)S: O(1)
Sort and check adjacent elements.
XOR
T: O(n)S: O(1)
XOR all elements. Duplicates cancel out, leaving the single number.
Common Mistakes
Using extra space when O(1) is required
Not understanding that XOR cancels out duplicate values
Using sum approach which fails if numbers are negative