Single Number XOR DSA Solution - Study Chapter | QuizMaker

Single Number explained with frequency map brute force, optimized XOR cancellation, dry run, edge cases, complexity, and Python, C++, Java code.

Read: 12m
Type: Chapter
Access: Free

Course

DSA Course: Interview Patterns and Problem Solving

Topic

Module 14: Bit Manipulation

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.

Input	Output	Why
`nums = [4,1,2,1,2]`	`4`	1 cancels with 1, 2 cancels with 2, and 4 remains.

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

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int answer = 0;
        for (int x : nums) {
            answer ^= x;
        }
        return answer;
    }
};

class Solution {
    public int singleNumber(int[] nums) {
        int answer = 0;
        for (int x : nums) {
            answer ^= x;
        }
        return answer;
    }
}

Sample Dry Run

Step	State	Result
Start	answer = 0	No value processed
XOR 4,1,2	answer changes with each value	Temporary result is not final yet
XOR second 1 and 2	Duplicate pairs cancel	Only 4 remains
Return	answer = 4	single number found

Complexity

Measure	Value	Reason
Time	O(n)	Each number is XORed once.
Space	O(1)	Only one answer variable is stored.

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

Why does XOR remove duplicates?

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

Why is space O(1)?

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

What is the core pattern?

XOR cancellation.