Single Number

You receive a non-empty list of integers nums. Every value in it occurs exactly twice, except for one value that occurs exactly once.

Return that lone value.

Aim for a solution that runs in linear time and uses only a constant amount of extra memory, so no sets, dictionaries or sorted copies of the list.

Example 1

Example 2

Example 3

Constraints

• 1 <= nums.length <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• Every element appears exactly twice, except one element that appears exactly once.

Pattern Path · Math, Bits & Strings · problem 32 of 169

Start simple

For each element, scan the whole list to count its occurrences and return the one whose count is 1: O(n²) time, O(1) space (or O(n) time with a hash map, but O(n) space).

The key idea

Use the bitwise XOR operator. It has three properties that fit this problem perfectly:

• x ^ x = 0: a value cancels itself out.
• x ^ 0 = x: zero changes nothing.
• XOR is commutative and associative, so you may regroup the terms in any order.

Fold the whole list into one running value with XOR. Mentally rearrange the terms so each pair sits next to its twin: every pair collapses to 0, and the 0s vanish, leaving only the lone value. The actual order of the list is irrelevant, which is why a single pass with one integer of state is enough.

Another way to see it: look at a single bit position. Each paired value contributes its bit an even number of times, so that bit flips back to where it started. Only the lone value flips bits an odd number of times.

Complexity

• Time: O(n)
• Space: O(1)

Python

class Solution:
    def singleNumber(self, nums):
        result = 0
        for x in nums:
            result ^= x  # pairs cancel out: x ^ x == 0
        return result

JavaScript

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

What the interviewer is checking

The interviewer wants to see whether you know XOR's self-cancelling property and can justify, not just recall, why it isolates the unpaired value under an O(1) memory limit.

Mistakes to avoid

• Reaching for a set or dictionary, which ignores the constant-memory requirement.
• Using arithmetic tricks like 2·sum(set) − sum(list): correct, but it still builds a set and can overflow in fixed-width languages.
• Starting the accumulator at something other than 0.

Follow-ups to expect

• What if every other value appears three times? (Count each bit modulo 3.)
• What if exactly two values appear once? (Split by a set bit of their XOR.)
• What if the list is sorted? (Binary search on pair alignment.)

In real software

XOR cancellation underpins RAID-5 parity, where any one missing disk block can be rebuilt by XOR-ing the surviving blocks.

Practice next