Single Number: XOR Cancellation Pattern

Learning Outcome

After this lesson, you should be able to use XOR cancellation to remove duplicate pairs without extra memory.

Problem Statement

Given an integer array where every element appears twice except one, return the single element.

Brute Force Approach

Use a frequency map and return the value with count 1. This is clear but uses extra memory.

Optimized Approach

XOR every value. Because x xor x = 0 and x xor 0 = x, duplicate pairs cancel out and the unique value remains.

Exact Pseudocode

answer = 0
for x in nums:
  answer = answer xor x
return answer
  

Reference Code

class Solution:
    def singleNumber(self, nums):
        answer = 0
        for x in nums:
            answer ^= x
        return answer
  

Sample Dry Run

Complexity

Edge Cases

• The trick assumes every non-answer value appears exactly twice.
• Negative numbers still work with XOR.
• Do not use addition as a replacement for XOR cancellation.

Interview Checklist

• Initialize answer to 0.
• XOR every number exactly once.
• State the XOR identities: x xor x = 0 and x xor 0 = x.

FAQs

Equal values XOR to zero, and XOR is associative and commutative, so pairs cancel regardless of order.

No map or set is needed; the running XOR holds the answer.

XOR cancellation.