Single Number
LeetCode #136 · Easy · Math · C++ solution with worked-out approach and complexity analysis.
Approach
XOR Bit Manipulation
Key insight
XOR has these properties: - a ^ a = 0 (same numbers cancel out) - a ^ 0 = a (XOR with 0 returns the number) - XOR is commutative and associative
Time
O(n)
Space
O(1)
Problem description(from LeetCode)
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
Example 1
- Input:
- nums = [2,2,1]
- Output:
- 1
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 once.
C++ Solution
solution.cpp
class Solution {
public:
int singleNumber(vector<int> &nums) {
int res = 0;
for (int num : nums) {
res ^= num;
}
return res;
}
};