Watch 10 video solutions for Single Number, a easy level problem involving Array, Bit Manipulation. This walkthrough by NeetCode has 117,983 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
You must implement a solution with a linear runtime complexity and use only constant extra space.
Example 1:
Input: nums = [2,2,1] Output: 1
Example 2:
Input: nums = [4,1,2,1,2] Output: 4
Example 3:
Input: nums = [1] Output: 1
Constraints:
1 <= nums.length <= 3 * 104-3 * 104 <= nums[i] <= 3 * 104Problem Overview: You get an integer array where every element appears exactly twice except for one element that appears once. Your task is to return that single number. The challenge is solving it efficiently without unnecessary extra work.
Approach 1: Hash Map (O(n) time, O(n) space)
The straightforward solution counts how many times each number appears. Iterate through the array and store frequencies in a hash map where the key is the number and the value is its count. After building the map, scan through the entries and return the element whose frequency is 1. This works because hash lookups and updates run in constant time on average. The trade‑off is extra memory proportional to the number of unique elements. This approach is intuitive and commonly used when you need frequency counting in array problems.
Approach 2: XOR Operation (O(n) time, O(1) space)
The optimal solution relies on properties of the XOR bitwise operator. XOR of a number with itself is 0, and XOR of a number with 0 is the number itself. Also, XOR is commutative and associative, meaning order does not matter. Iterate through the array and XOR every element into a running variable. All duplicate numbers cancel each other out because a ^ a = 0. After processing the entire array, only the unique element remains in the accumulator. This approach uses constant extra space and a single pass through the array.
The key insight is recognizing that pairwise duplicates can eliminate themselves using bitwise operations. This pattern appears frequently in bit manipulation problems where duplicates occur in predictable counts.
Recommended for interviews: The XOR approach is what most interviewers expect. It demonstrates understanding of bitwise properties and achieves the optimal O(n) time with O(1) extra space. The hash map approach still shows correct reasoning and is often the first step many candidates describe before optimizing. Showing both approaches communicates problem‑solving progression and awareness of trade‑offs.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map Frequency Count | O(n) | O(n) | Good first approach when counting occurrences or when the duplicate pattern is not guaranteed |
| XOR Bit Manipulation | O(n) | O(1) | Best choice for this problem when every element appears exactly twice except one |