Single Number III

Medium
408.

Single Number III

Single Number III is a medium coding problem on arrays and bit manipulation, asked in Amazon, Google, Meta and Zomato interviews.

In an integer array nums, exactly two elements appear only once and all the others appear exactly twice.

Find the two loners and return them sorted in ascending order. Aim for linear time and constant extra space.

Example 1

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

Example 2

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

Example 3

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

Constraints

  • 2 <= nums.length <= 40
  • -1000000 <= nums[i] <= 1000000
  • Exactly two elements appear once; every other element appears twice.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var singleNumber = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Single Number III — Solution in Python, Java & C++

Single Number III solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Single Number III is a medium coding problem on arrays and bit manipulation, asked in Amazon, Google, Meta and Zomato interviews.

  • Difficulty: Medium
  • Topics: Arrays, Bit Manipulation
  • Asked at: Amazon, Google, Meta, Zomato
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

In an integer array nums, exactly two elements appear only once and all the others appear exactly twice.

Find the two loners and return them sorted in ascending order. Aim for linear time and constant extra space.

Example 1

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

Example 2

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

Example 3

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

Constraints

  • 2 <= nums.length <= 40
  • -1000000 <= nums[i] <= 1000000
  • Exactly two elements appear once; every other element appears twice.

Hints for Single Number III

  1. Hint 1

    XOR everything: the pairs cancel and you are left with a ^ b.

  2. Hint 2

    Since a != b, that XOR has at least one set bit — pick the lowest one with x & -x.

  3. Hint 3

    That bit splits the array into two groups, each containing exactly one loner; XOR each group separately.

How to solve Single Number III

XOR everything to get a ^ b; any set bit of that value separates a from b. Partition the array on the lowest such bit and XOR each group independently.

Approach

  1. Compute xorAll over the array.
  2. Take lowBit = xorAll & -xorAll.
  3. XOR the numbers with that bit set into a, the rest into b; return them sorted.

Why it works

Pairs land in the same group and cancel, while a and b differ at lowBit and so land in different groups — each group's XOR is therefore one loner.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • x & -x isolates the lowest set bit in two's complement.

Reference solution

Python

def singleNumber(nums):
    xor_all = 0
    for x in nums:
        xor_all ^= x
    low_bit = xor_all & -xor_all
    a = b = 0
    for x in nums:
        if x & low_bit:
            a ^= x
        else:
            b ^= x
    return [a, b] if a < b else [b, a]

Java

public static int[] singleNumber(int[] nums) {
    int xorAll = 0;
    for (int x : nums) xorAll ^= x;
    int lowBit = xorAll & -xorAll;
    int a = 0, b = 0;
    for (int x : nums) {
        if ((x & lowBit) != 0) a ^= x;
        else b ^= x;
    }
    return a < b ? new int[]{a, b} : new int[]{b, a};
}

C++

vector<int> singleNumber(vector<int>& nums) {
    int xorAll = 0;
    for (int x : nums) xorAll ^= x;
    int lowBit = xorAll & -xorAll;
    int a = 0, b = 0;
    for (int x : nums) {
        if ((x & lowBit) != 0) a ^= x;
        else b ^= x;
    }
    if (a < b) return vector<int>{a, b};
    return vector<int>{b, a};
}

JavaScript

var singleNumber = function(nums) {
    let xorAll = 0;
    for (let i = 0; i < nums.length; i++) xorAll ^= nums[i];
    const lowBit = xorAll & -xorAll;
    let a = 0, b = 0;
    for (let i = 0; i < nums.length; i++) {
        if ((nums[i] & lowBit) !== 0) a ^= nums[i];
        else b ^= nums[i];
    }
    return a < b ? [a, b] : [b, a];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Bit Manipulation