Skip to main content
Talentd

Single Number III - Solution & Explanation

MediumArrayBit Manipulation18 min readAsked at: Amazon, Microsoft, Siemens +4
Practice this problem

Problem Statement

Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.

You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.

 

Example 1:

Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation:  [5, 3] is also a valid answer.

Example 2:

Input: nums = [-1,0]
Output: [-1,0]

Example 3:

Input: nums = [0,1]
Output: [1,0]

 

Constraints:

  • 2 <= nums.length <= 3 * 104
  • -231 <= nums[i] <= 231 - 1
  • Each integer in nums will appear twice, only two integers will appear once.

Approach Overview

Problem Overview: You're given an integer array where every element appears exactly twice except for two numbers that appear once. The task is to return those two unique values. Order does not matter, but the solution should run in linear time and ideally constant extra space.

Approach 1: Counting with HashMap (O(n) time, O(n) space)

The straightforward solution uses a frequency map. Iterate through the array and store counts in a hash map where the key is the number and the value is its frequency. After building the map, iterate through the entries and collect the numbers with frequency 1. Since all other numbers appear exactly twice, the two values with count 1 are the answer.

This approach relies on constant‑time hash lookups and works well for quick implementation. The tradeoff is memory usage: the hash map can grow up to O(n) in the worst case. It mainly serves as a conceptual baseline before optimizing with bit tricks. Related concepts appear often in hash table problems involving frequency counting.

Approach 2: XOR and Partitioning (O(n) time, O(1) space)

The optimal solution uses properties of XOR. First XOR all elements in the array. Since a ^ a = 0, every duplicated value cancels out. The final XOR result equals x ^ y, where x and y are the two unique numbers.

The key insight: if x ^ y is non‑zero, at least one bit differs between them. Extract the rightmost set bit using diff = xor & -xor. This bit acts as a partition. Iterate through the array again and divide numbers into two groups based on whether this bit is set. Because duplicates share identical bits, they fall into the same group and cancel via XOR. Each partition eventually produces one of the unique numbers.

This technique keeps memory usage constant and requires only two passes over the array. It is a classic application of bit manipulation combined with simple iteration over an array. The partitioning trick appears frequently in interview problems involving XOR identities.

Recommended for interviews: Interviewers typically expect the XOR partitioning solution. The HashMap approach shows that you understand the problem and can build a correct baseline, but the XOR method demonstrates deeper knowledge of bit operations and space optimization. If time permits, explain the HashMap idea briefly and then implement the XOR solution for the final answer.

Approach 1: XOR and Partitioning

The idea is to use the XOR operation to find two unique numbers that appear only once in the array. This can be achieved by:

  1. Performing XOR for all numbers, resulting in a XOR b.
  2. Finding a set bit where a and b differ.
  3. Partitioning the elements into two groups based on this set bit and XOR within each group.
  4. This technique uses linear time and constant space.

This C program uses bitwise XOR to isolate the unique numbers. The key step is identifying a differing bit to partition the numbers, allowing separation of the unique numbers in linear time.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), constant space is used for variables non-dependent on input size.

Try this approach in the editor →

Approach 2: Counting with HashMap (Conceptual)

An alternative approach that utilizes hash maps to count occurrences of each element would typically find the unique numbers. Although this solution is more straightforward, it requires additional space and does not strictly meet the problem constraints of constant extra space.

This Python solution leverages collections.Counter to track occurrences and quickly find numbers appearing only once. While simple, it utilizes additional space beyond the constraints of the problem for learning purposes.

Code

Python

Python

Complexity

Time Complexity: O(n), for passing through the array for counting.
Space Complexity: O(n), as space is allocated for counts of numbers.

Try this approach in the editor →

Approach 3: Bitwise Operation

The XOR operation has the following properties:

  • Any number XOR 0 is still the original number, i.e., x \oplus 0 = x;
  • Any number XOR itself is 0, i.e., x \oplus x = 0;

Since all numbers in the array appear twice except for two numbers, we can perform XOR operation on all numbers in the array to get the XOR result of the two numbers that only appear once.

Since these two numbers are not equal, there is at least one bit that is 1 in the XOR result. We can use the lowbit operation to find the lowest bit of 1 in the XOR result, and divide all numbers in the array into two groups based on whether this bit is 1 or not. This way, the two numbers that only appear once are separated into different groups.

Perform XOR operation on each group separately to obtain the two numbers a and b that only appear once.

The time complexity is O(n), where n is the length of the array. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

Try this approach in the editor →

Approach 4: Hash Table

Code

TypeScriptJavaScript

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
XOR and Partitioning

Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), constant space is used for variables non-dependent on input size.

Counting with HashMap (Conceptual)

Time Complexity: O(n), for passing through the array for counting.
Space Complexity: O(n), as space is allocated for counts of numbers.

Bitwise Operation—
Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Counting with HashMapO(n)O(n)Quick baseline solution when memory constraints are not strict
XOR and PartitioningO(n)O(1)Optimal interview solution with constant extra space

Video Solution

Single Number iii | LeetCode 260 | C++, Java, Python3 • Knowledge Center • 18,649 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Single Number III easy or hard?
Single Number III is rated Medium on LeetCode. The difficulty comes from recognizing the XOR partition trick. Once the bit manipulation insight is known, the implementation itself is short and runs in linear time.
How to solve Single Number III in O(n)?
First XOR all elements so duplicates cancel out, leaving xor = x ^ y where x and y are the unique numbers. Extract a differentiating bit using diff = xor & -xor. Partition numbers based on that bit and XOR each group separately to recover x and y. This requires two linear passes and constant space.
What is the best approach for Single Number III?
The XOR partitioning approach is considered the best solution. It XORs all numbers to get the combined difference of the two unique values, then isolates a distinguishing bit to split the array into two groups. Each group is XORed again to recover the two single numbers. The algorithm runs in O(n) time with O(1) extra space.
What data structure is used in Single Number III?
The optimal solution mainly uses bit manipulation with XOR operations and simple variables, not additional data structures. A simpler alternative uses a hash map to count frequencies, which requires O(n) extra space but is easier to implement.
What is the time complexity of Single Number III?
The optimal algorithm runs in O(n) time because it scans the array twice: once to compute the combined XOR and once to partition numbers by a distinguishing bit. The space complexity is O(1) since only a few integer variables are used regardless of input size.
Single Number III Python or Java solution approach?
Both Python and Java implementations typically follow the XOR partitioning technique. Compute the combined XOR, isolate the rightmost set bit, then iterate through the array to XOR numbers into two partitions. Each partition produces one of the unique values.
Is Single Number III asked at Google, Amazon, or Meta?
Bit manipulation problems similar to Single Number III appear in interviews at large tech companies including Amazon, Google, and Meta. The question tests understanding of XOR properties, bit masking, and space‑optimized problem solving.

Ready to solve this problem?

Practice Single Number III with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find The Original Array of Prefix Xor

Next

Find the XOR of Numbers Which Appear Twice