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:
Input: nums = [2,2,1]
Output: 1
Example 2:
Input: nums = [4,1,2,1,2]
Output: 4
Example 3:
Input: nums = [1]
Output: 1
Constraints:
1 <= nums.length <= 3 * 104
-3 * 104 <= nums[i] <= 3 * 104
This problem asks to find the unique number in an array where all other numbers appear twice. The most efficient solution leverages the properties of the bitwise XOR (^) operator.
Understanding the XOR Operator:
The XOR operator has two crucial properties for this problem:
x ^ 0 = x
(XORing with 0 leaves the number unchanged).x ^ x = 0
(XORing a number with itself results in 0).Algorithm:
The algorithm is remarkably simple:
result
to 0.nums
.num
in nums
, perform a XOR operation between result
and num
: result = result ^ num
.Because of the involution property, when a number appears twice, its XOR operations cancel each other out, resulting in 0. The unique number, appearing only once, will remain in result
.
Time and Space Complexity:
result
variable.Code Implementation (Python):
def singleNumber(nums):
result = 0
for num in nums:
result ^= num
return result
#Example Usage
nums = [2,2,1]
print(singleNumber(nums)) # Output: 1
nums = [4,1,2,1,2]
print(singleNumber(nums)) # Output: 4
Code Implementation (Java):
class Solution {
public int singleNumber(int[] nums) {
int result = 0;
for (int num : nums) {
result ^= num;
}
return result;
}
}
Code Implementation (C++):
class Solution {
public:
int singleNumber(vector<int>& nums) {
int result = 0;
for (int num : nums) {
result ^= num;
}
return result;
}
};
Other Languages: The implementations in other languages (JavaScript, Go, TypeScript, Rust, C#, C, Swift etc.) follow the same basic structure, iterating through the array and applying the XOR operation. The specific syntax may vary slightly depending on the language, but the core logic remains consistent. The use of reduce
function as shown in some solutions offers a more concise way to express the same logic.
Alternative Approaches (Less Efficient):
While the XOR approach is optimal, alternative approaches exist but are less efficient:
In summary, the bitwise XOR operation provides an elegant and highly efficient solution to this problem, meeting the requirements of linear time and constant space complexity.