87. Single Number · DSA Practice

Every element appears twice except one. Find that one in O(n) time and O(1) extra space.

Example 1

Input: nums = [2,2,1]

Output: 1

Example 2

Input: nums = [4,1,2,1,2]

Output: 4

Hint 1

XOR of a number with itself is 0.

Bit Manipulation

Approach 1: Hash set

Add/remove values; one remains.

⏱ Time O(n)💾 Space O(n)

Approach 2: XOR everything ✅

Duplicates cancel.

⏱ Time O(n)💾 Space O(1)

Reference solution for XOR everything (time O(n), space O(1)). Each solution passes every test in all four languages.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        x = 0
        for v in nums:
            x ^= v          # a ^ a = 0 and a ^ 0 = a, so pairs cancel
        return x

class Solution {
    public int singleNumber(int[] nums) {
        int x = 0;
        for (int v : nums) x ^= v;   // pairs cancel out
        return x;
    }
}

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int x = 0;
        for (int v : nums) x ^= v;   // pairs cancel out
        return x;
    }
};

function singleNumber(nums) {
  let x = 0;
  for (const v of nums) x ^= v; // pairs cancel out
  return x;
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

This problem is explained in the lesson Bit Manipulation.