Skip to content

Single Number⚓︎

Link

Description⚓︎

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⚓︎

Some properties of XOR operator:

  • Commutative law: x ^ y ^ z == x ^ z ^ y;
  • 0 ^ n == n;
  • n ^ n == 0.
1
2
3
4
5
6
7
8
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (int num : nums) res ^= num;
        return res;
    }
};
  • Time complexity: \(O(n)\);
  • Space complexity: \(O(1)\).