Problem statement
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 * 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.
Solution 1: Counting the appearances
Count how many times each element appears in the array. Then return the one appearing only once.
Code
#include <vector>
#include <iostream>
#include <unordered_map>
using namespace std;
int singleNumber(vector<int>& nums) {
unordered_map<int, int> count;
for (int n : nums) {
count[n]++;
}
int single;
for (auto& pair : count) {
if (pair.second == 1) {
single = pair.first;
break;
}
}
return single;
}
int main() {
vector<int> nums{2,2,1};
cout << singleNumber(nums) << endl;
nums = {4,1,2,1,2};
cout << singleNumber(nums) << endl;
nums = {1};
cout << singleNumber(nums) << endl;
}
Output:
1
4
1
Complexity
Runtime:
O(N)
, whereN = nums.length
.Extra space:
O(N)
(not constant, need another solution).
Solution 2: Bitwise exclusive OR
You can also use the bitwise XOR operator to cancel out the duplicated elements in the array. The remain element is the single one.
a XOR a = 0.
a XOR 0 = a.
Code
#include <vector>
#include <iostream>
using namespace std;
int singleNumber(vector<int>& nums) {
int single = 0;
for (int n : nums) {
single ^= n;
}
return single;
}
int main() {
vector<int> nums{2,2,1};
cout << singleNumber(nums) << endl;
nums = {4,1,2,1,2};
cout << singleNumber(nums) << endl;
nums = {1};
cout << singleNumber(nums) << endl;
}
Output:
1
4
1
Complexity
Runtime:
O(N)
, whereN = nums.length
.Extra space:
O(1)
.
References
Thanks for reading. Feel free to share your thought about my content and check out my FREE book “10 Classic Coding Challenges”.
Did you find this article valuable?
Support LeetSolve by becoming a sponsor. Any amount is appreciated!