Command Palette

Search for a command to run...

Hectal
Problem 34.7 · Bit ManipulationMedium

Single Number III

PatternBit Manipulation

What it teaches: Split by one differing bit to isolate two singles.

Practise it on judges as “Single Number III”.

The problem

Exactly two elements appear once and all others twice. Return the two singles in any order, using O(1) extra space.

Example 1

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

Constraints

  • 2 ≤ n ≤ 3 × 10⁴

Pattern clues in the wording

  • → Two unpaired values

These clues point to Bit Manipulation: Use XOR, AND, OR and shifts to test, set and cancel bits, often in O(1) space.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public int[] singleNumber(int[] nums) {
        return new int[2];
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
nums = [1,2,1,3,2,5]
[3,5]
2
nums = [-1,0]
[-1,0]
3
nums = [0,1]
[1,0]

From slow to fast

Approaches

1. XOR then split · O(n)
1

XOR then split

Time O(n) Space O(1)

diff = lowest set bit of (a ^ b). XOR the numbers with that bit set to get a; b = (a ^ b) ^ a.

Approach 1
class Solution {
    public int[] singleNumber(int[] nums) {
        int both = 0;
        for (int x : nums) both ^= x;
        int diff = both & -both;
        int a = 0;
        for (int x : nums) if ((x & diff) != 0) a ^= x;
        return new int[]{a, both ^ a};
    }
}

Verdict: Two passes of XOR.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Negative values
  • both == Integer.MIN_VALUE (diff is the sign bit, still fine)

Mistakes people make

  • Checking (x & diff) == 1 instead of != 0.

Interview

Follow-up questions

Why do pairs stay together after the split?