Single Number — Problem Statement & Solution Guide
Problem Description
You are given an integer array nums that contains at least one element. Every value in the array occurs exactly twice except for a single value that appears only once. Write a function that returns this solitary value. The solution must run in linear time and use only constant extra space.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Single Number"
WHY DOES IT MATTER?
The XOR‑based pattern demonstrates how algebraic properties of bitwise operators can replace auxiliary data structures, enabling constant‑space solutions for problems involving pairing or cancellation.
OPTIMIZATION CHALLENGE
The key insight is recognizing that duplicate values nullify each other under XOR, turning a seemingly O(n) memory problem into a simple accumulator loop that runs in linear time with O(1) extra space.
REAL-WORLD CONNECTION
In distributed systems, XOR is used for parity calculations in RAID‑5 storage: each disk stores a parity block computed via XOR, allowing reconstruction of a lost disk without extra metadata.
During an interview, write the XOR accumulation loop first, then immediately discuss edge cases (e.g., negative numbers) to show you understand two's complement representation and that XOR works uniformly across signed integers.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The classic "Single Number" problem is a perfect illustration of how bitwise XOR (^) can be leveraged to cancel out duplicate elements. XOR has two crucial properties: it is commutative and associative, and any number XORed with itself yields zero (a ^ a = 0). When you XOR all elements of the array, every pair of identical numbers nullifies each other, leaving only the unique element as the final result. Naïve solutions—such as using a hash map to count frequencies or sorting the array—require O(n) extra space or O(n log n) time, which become prohibitive for massive data streams or memory‑constrained environments. The optimal paradigm exploits the constant‑space, linear‑time nature of bitwise operations, making it ideal for in‑place processing of large-scale integer collections.
Interview Questions on This Problem
Q1How would you modify the solution if every element appears three times except for one that appears once?
Use bitwise counters for each bit position: sum the bits across all numbers modulo 3, then reconstruct the unique number from these remainders. This runs in O(n) time and O(1) space.
Q2Why can't we simply sort the array and then scan for the non‑duplicate element?
Sorting incurs O(n log n) time, which violates the linear‑time requirement, and it also modifies the input order, which may be disallowed in certain interview constraints.
Q3Explain how XOR can be used to find the missing number in an array containing numbers from 1 to n with one missing element.
Compute XOR of all indices 1..n and XOR of all array elements; the XOR of these two results yields the missing number because all present numbers cancel out.
Examples
Input
[4, 1, 2, 1, 2]
Output
4
Explanation: The numbers 1 and 2 each appear twice. The number 4 appears only once, so the function returns 4.
Input
[7, 3, 5, 3, 5, 7, 9]
Output
9
Explanation: Pairs (7,7), (3,3) and (5,5) cancel each other out. The remaining element is 9, which is returned.
Input
[0, -1, -1]
Output
0
Explanation: The value -1 occurs twice, leaving 0 as the unique element.
Constraints
- 1 <= nums.length <= 100000
- Each element fits in a signed 32‑bit integer: -2^31 <= nums[i] <= 2^31 - 1
- All elements except one appear exactly twice
Optimal Approach & Strategy
Initialize a variable result = 0 and XOR it with each element of the array in a single loop. After processing all numbers, result holds the single non‑duplicate value. This achieves O(n) time and O(1) space.
Brute Force Approach
Iterate through the array and store each number's frequency in a hash map, then scan the map for the entry with count 1. This uses O(n) extra space and requires two passes over the data.
Verified Code Solutions
function solution(nums) { let result = 0; for (let num of nums) { result ^= num; } return result; }class Solution {public: int solution(vector<int>& nums) { int result = 0; for (int num : nums) { result ^= num; } return result; }}class Solution { public int solution(int[] nums) { int result = 0; for (int num : nums) { result ^= num; } return result; } }def solution(nums): result = 0; for num in nums: result ^= num; return resultfunction solution(nums) { let result = 0; for (let num of nums) { result ^= num; } return result; }Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.