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 * 104The #136 Single Number problem asks you to find the element that appears only once in an array where every other element appears exactly twice. A straightforward way to think about this is using a hash-based structure such as a set or map to track occurrences, but this requires extra memory.
The most efficient and commonly expected solution in interviews uses bit manipulation, specifically the XOR operation. XOR has two important properties: a ^ a = 0 and a ^ 0 = a. When you XOR all numbers in the array together, duplicate values cancel each other out, leaving only the unique element. This allows the algorithm to run in a single pass while using constant extra space.
This elegant property makes XOR the optimal strategy for this problem. The approach works in linear time and avoids additional memory, making it ideal for coding interviews where efficiency and simplicity are valued.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Set / Hash Map Counting | O(n) | O(n) |
| Bit Manipulation (XOR) | O(n) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Think about the XOR (^) operator's property.
This approach leverages the properties of XOR bitwise operation. The XOR of a number with itself is 0, and the XOR of a number with 0 is the number itself. Thus, XORing all elements in the array results in getting the single number because all other numbers cancel themselves out.
Time Complexity: O(n) - We go through the array once.
Space Complexity: O(1) - We only use a single integer to store the result.
1function singleNumber(nums) {
2 let result = 0;
3 for (let num of nums) {
4 result ^= num;
5
This JavaScript function iterates over the nums array, utilizing the XOR operation to eliminate duplicates, leaving behind the single number.
In this approach, we use a hash map (or dictionary) to count occurrences of each number. The single number will have a count of 1. This isn't the optimal solution in terms of extra space but is valid if space was not constrained.
Time Complexity: O(n) - We traverse the array twice (once for filling the map, once for checking the counts).
Space Complexity: O(n) - Extra space proportional to the input range.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Single Number is a common interview question at companies like Amazon, Google, and Meta. It tests understanding of bit manipulation and the ability to recognize patterns that lead to optimal constant-space solutions.
The optimal approach uses the XOR bit manipulation technique. Since a ^ a = 0 and a ^ 0 = a, XORing all numbers cancels out duplicates and leaves the unique number. This method runs in O(n) time with O(1) extra space.
While a hash set or hash map can track frequencies, the best approach does not require any extra data structure. Using the XOR operation allows you to compute the result in constant space while iterating through the array once.
XOR works because identical numbers cancel each other out when XORed together. Since every number except one appears twice, all duplicate pairs become zero, leaving only the single unique element.
This Java method employs a HashMap to tally number occurrences, ultimately finding the number with a singular count.