136. Single Number
Model: qwen2.5-coder:14b
Topics: Hash Table,Bit Manipulation
FAANG asked: 1
Acceptance rate: 66.7%
Problem Breakdown
The problem asks us to find the single number in an array where every other number appears exactly twice. The input is a non-empty list of integers, and the output should be the integer that appears only once. The constraints include the range of numbers and the fact that all numbers except one appear twice.
Key points:
- Input: A list of integers
numswith length between 1 and 30,000. - Output: An integer that appears exactly once in the list.
- Constraint: All other integers appear exactly twice.
- Edge cases: The list could contain negative numbers, and the single number could be at any position.
Intuition
A brute-force approach would involve using a hash table to count occurrences of each number. This would work but would require extra memory proportional to the number of unique elements in the array (O(n) space complexity). Additionally, it would have a time complexity of O(n) due to iterating through the list twice.
The key insight is that we can use bitwise XOR operation to solve this problem without extra memory and with linear runtime. The XOR operation has a few useful properties:
a ^ a = 0for any integera.a ^ 0 = afor any integera.- XOR is commutative and associative, meaning the order of operations does not matter.
Given these properties, if we XOR all numbers in the array together, pairs of identical numbers will cancel each other out (resulting in 0), leaving only the single number that appears once.
Approach
- Initialize a variable
singleto 0. - Iterate through each number in the list
nums. - For each number, apply the XOR operation between
singleand the current number. - After processing all numbers,
singlewill hold the value of the number that appears only once.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the input list
nums. We iterate through the list once. - Space Complexity: O(1). We use a constant amount of extra space regardless of the input size.
Solution
def singleNumber(nums):
single = 0
for num in nums:
single ^= num
return single
Edge Cases Handled
- Single element list: If the list contains only one element, the algorithm will correctly return that element.
- Negative numbers: The XOR operation works with negative numbers as well, so the presence of negative numbers does not affect the solution.
- All elements are the same except one: The algorithm will correctly identify the single different element.
The provided solution is correct and efficient. It meets all the requirements specified in the problem statement, including handling edge cases and maintaining linear time complexity with constant space complexity.