Single Number I
Given a non-empty array of integers, every element appears twice except for one. Find that single one. You must implement a solution with 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
Solution Code
class Solution {
public:
int singleNumber(vector& nums) {
int exor = 0;
for(int i = 0; i < nums.size(); i++) {
exor = exor ^ nums[i];
}
return exor;
}
};
Solution Explanation
The problem requires finding a unique number in an array where every other number appears exactly twice. The solution uses the XOR bitwise operator to find the unique number as follows:
- XOR Operation: XOR-ing a number with itself results in 0, and XOR-ing with 0 results in the number itself. Hence, when you XOR all numbers in the array, pairs will cancel each other out, leaving only the unique number.
- Linear Runtime Complexity: This approach runs in O(n) time, where n is the number of elements in the array, making it efficient for this problem.
- Constant Extra Space: The solution uses only one extra variable (`exor`), hence the space complexity is O(1).