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- Each element in the array appears twice except for one element which appears only once.
Companies:
SAP, Amazon, Microsoft, Adobe, Facebook, Yahoo
Related Topics:
Array, Bit Manipulation
Similar Questions:
- Single Number II (Medium)
- Single Number III (Medium)
- Missing Number (Easy)
- Find the Duplicate Number (Medium)
- Find the Difference (Easy)
// OJ: https://leetcode.com/problems/single-number/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans = 0;
for (int n : nums) ans ^= n;
return ans;
}
};