#260

Medium

LeetCode Problem Workspace

Single Number III

Find the two unique numbers in an array where all other numbers appear exactly twice using bit manipulation efficiently.

array bit manipulation

Problem Statement

Given an integer array nums, exactly two elements appear only once while all other elements appear exactly twice. Return the two unique numbers in any order using an efficient algorithm.

Your solution must run in linear time and use constant extra space. For example, given nums = [1,2,1,3,2,5], a valid output is [3,5].

Examples

Example 1

Input: nums = [1,2,1,3,2,5]

Output: [3,5]

[5, 3] is also a valid answer.

Example 2

Input: nums = [-1,0]

Output: [-1,0]

Example details omitted.

Example 3

Input: nums = [0,1]

Output: [1,0]

Example details omitted.

Constraints

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

Solution Approach

Use XOR to find combined difference

XOR all numbers in nums to get xorResult which equals the XOR of the two unique numbers. This works because duplicates cancel out, leaving only the XOR of the single numbers.

Find a distinguishing bit

Locate any set bit in xorResult; this bit differs between the two unique numbers. Use this bit to partition nums into two groups where each group contains one unique number and its duplicates.

Separate and identify unique numbers

XOR numbers within each partitioned group to isolate each unique number. Each group reduces to a single unique number while duplicates cancel out, producing the final result in constant space and linear time.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because every number is XORed twice, once for the total xorResult and once in partitioning. Space complexity is O(1) as only a few variables are needed for XOR calculations.

What Interviewers Usually Probe

Expect a linear time and constant space solution using bitwise operations.
They may hint at XOR or ask how to distinguish two unique numbers.
Watch for questions about edge cases like negative numbers or minimal array length.

Common Pitfalls or Variants

Common pitfalls

Attempting to use a hash map violates constant space requirement.
Not correctly identifying the distinguishing bit can mix up the two unique numbers.
Forgetting that XOR of duplicates cancels out may lead to incorrect grouping.

Follow-up variants

Single Number I: Only one unique number appears, all others twice.
Single Number II: Every number appears three times except one unique number.
Find k unique numbers using generalized bit manipulation and partitioning.

FAQ

What is the main trick to solve Single Number III efficiently?

The key is using XOR to combine numbers and then leveraging a distinguishing bit to separate the two unique numbers.

Can I solve this using extra data structures like sets or hash maps?

While possible, using extra structures violates the constant space constraint of the problem.

Does the order of the output matter for Single Number III?

No, the two unique numbers can be returned in any order.

How does bit manipulation help in this array problem?

Bit manipulation allows duplicates to cancel via XOR and isolates unique numbers efficiently in linear time without extra space.

Are negative numbers handled correctly in Single Number III?

Yes, XOR and bitwise operations work with negative numbers, so the algorithm handles all integer values within constraints.

terminal

Solution

Solution 1: Bitwise Operation

The XOR operation has the following properties:

1

2

3

4

5

6

7

8

9

10

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        xs = reduce(xor, nums)
        a = 0
        lb = xs & -xs
        for x in nums:
            if x & lb:
                a ^= x
        b = xs ^ a
        return [a, b]

Solution 2: Hash Table

#### TypeScript

1

2

3

4

5

6

7

8

9

10

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        xs = reduce(xor, nums)
        a = 0
        lb = xs & -xs
        for x in nums:
            if x & lb:
                a ^= x
        b = xs ^ a
        return [a, b]

Continue Practicing

#268 missing number #287 find the duplicate number #318 maximum product of word lengths