☕ DSA Java Articles

Topics › Bit Manipulation › Interview Problems

Single Number - III

Medium TUF ID 145 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an integer array nums in which every value appears exactly twice, except for two distinct values that each appear exactly once. Return those two values. The judge accepts them in any order; the solutions below return them in increasing order so that results are easy to compare. The follow-up, as with the other Single Number problems, is to do it in linear time and constant extra space.

Constraints: 2 ≤ n ≤ 3 × 10^4, n is even, values fit in a 32-bit signed integer (negatives allowed). Exactly two values occur once, all others occur exactly twice.

Example 1

nums = [1, 2, 1, 3, 2, 5]
answer = [3, 5]      // 1 and 2 are paired; 3 and 5 are alone

Example 2

nums = [-1, 0]
answer = [-1, 0]     // the smallest valid input: both elements are single

Example 3

nums = [8, 24, 100, 100]
answer = [8, 24]

Approach 1: Brute force

Intuition. Count occurrences directly. For each element, scan the array and tally its value; collect the elements whose tally is 1. Stop as soon as both have been found. This is a verbatim implementation of the definition and costs a full scan per element.

Algorithm.

  1. For each index i, while fewer than two singles have been found:
  2. Count how many indices j satisfy nums[j] == nums[i].
  3. If the count is 1, record nums[i].
  4. Sort the two recorded values and return them.
static int[] bruteForce(int[] nums) {
    int n = nums.length;
    int[] result = new int[2];
    int found = 0;
    for (int i = 0; i < n && found < 2; i++) {
        int count = 0;
        for (int j = 0; j < n; j++) {
            if (nums[j] == nums[i]) count++;
        }
        if (count == 1) result[found++] = nums[i];
    }
    Arrays.sort(result);
    return result;
}

Complexity. Time O(n^2): up to n inner scans of length n. Space O(1) beyond the two-element output.

Approach 2: Better, frequency map

Intuition. Count every value once with a hash map instead of recounting. After one pass, the two keys with count 1 are the answer. This is simple and robust, and it is the approach that still works when the “everything else appears twice” guarantee is replaced by something odd; its cost is O(n) extra memory.

Algorithm.

  1. Build freq, a map from value to count, in one pass.
  2. Walk the entries and collect the two keys whose count is 1.
  3. Sort the pair and return it.
static int[] better(int[] nums) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int x : nums) freq.merge(x, 1, Integer::sum);
    int[] result = new int[2];
    int found = 0;
    for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
        if (e.getValue() == 1) result[found++] = e.getKey();
    }
    Arrays.sort(result);
    return result;
}

Complexity. Time O(n): one pass to count plus one pass over at most n entries. Space O(n) for the map.

Approach 3: Optimal, XOR and split on a differing bit

Intuition. XOR of the whole array cancels every pair (x ^ x = 0), leaving xorAll = a ^ b, where a and b are the two singles. That alone does not reveal a or b, but it reveals something about them: every set bit of a ^ b is a position where a and b differ. Pick any such bit, say the lowest one. Now partition the array into two buckets: elements with that bit clear, and elements with that bit set. Two equal values land in the same bucket (they have identical bits), so every pair still cancels within its bucket. But a and b land in different buckets, because they differ at that bit. XOR each bucket and each one yields exactly one single.

The lowest set bit of v is v & -v. In two’s complement, -v flips every bit above the lowest set bit and keeps the lowest set bit and the zeros below it, so the AND isolates that single bit. Integer.lowestOneBit(v) does the same.

Algorithm.

  1. XOR all elements into xorAll (equals a ^ b).
  2. lowestBit = xorAll & -xorAll.
  3. For each x: if (x & lowestBit) == 0 XOR it into bucket0, else into bucket1.
  4. Return {bucket0, bucket1} sorted.
static int[] optimal(int[] nums) {
    int xorAll = 0;
    for (int x : nums) xorAll ^= x;             // pairs cancel, so this is a ^ b
    int lowestBit = xorAll & -xorAll;           // a and b differ at this bit, so it separates them
    int bucket0 = 0, bucket1 = 0;
    for (int x : nums) {
        if ((x & lowestBit) == 0) bucket0 ^= x; else bucket1 ^= x;
    }
    int[] result = {bucket0, bucket1};
    Arrays.sort(result);
    return result;
}

Dry run on nums = [1, 2, 1, 3, 2, 5]. First pass: 1 ^ 2 ^ 1 ^ 3 ^ 2 ^ 5 = 3 ^ 5 = 011 ^ 101 = 110 = 6. Lowest set bit of 6 is 010 = 2, so we split on bit 1.

x binary bit 1 bucket0 after bucket1 after
1 001 0 001 000
2 010 1 001 010
1 001 0 000 010
3 011 1 000 001
2 010 1 000 011
5 101 0 101 011

bucket0 = 5, bucket1 = 3; sorted, the answer is [3, 5]. Both 1s went to bucket 0 and both 2s to bucket 1, and each pair cancelled where it landed.

Complexity. Time O(n): two linear passes. Space O(1): three integers.

Why does the choice of bit not matter? Any set bit of a ^ b separates a from b, and pairs always stay together regardless of which bit you pick. The lowest set bit is simply the cheapest to isolate.

Edge cases and pitfalls