Find the two non-repeating elements in an array of repeating elements

The problem, simply

You get an array of numbers. Every number shows up exactly twice, except two numbers that show up only once. Find those two numbers and give them back, smaller one first.

The hard part is doing it with only a few extra variables, no map and no sorting.

A story to remember it

Picture it

Examples

Way 1: the simple way

Count how many times each number shows up, then keep the ones with count 1.

1. Walk the array and count each number in a hash map.
2. Walk again and collect the numbers whose count is 1.
3. Put the smaller one first.

import java.util.*;

class Solution {
    public static int[] findTwoNonRepeating(int[] arr) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int x : arr) count.merge(x, 1, Integer::sum);   // tally each number
        List<Integer> alone = new ArrayList<>();
        for (int x : arr) {
            if (count.get(x) == 1) alone.add(x);              // shows up once
        }
        int a = alone.get(0), b = alone.get(1);
        return a < b ? new int[]{a, b} : new int[]{b, a};
    }
}

How long it takes: two walks, O(n). Extra room: the map holds about n / 2 numbers, O(n). Checking each number against all others with two loops would also work but takes O(n^2).

Way 2: the clever way

XOR has two rules: x ^ x = 0 and x ^ 0 = x. The order does not matter.

1. XOR every number together. Twins cancel, so you get xor = a ^ b, where a and b are the loners.
2. a and b are different, so xor has at least one 1. A 1 there means a and b differ at that bit. Keep the lowest one with xor & -xor.
3. Split the array by that bit. Twins share all bits, so both twins land on the same side. a and b land on different sides.
4. XOR each side on its own. Each side's twins cancel and leave one loner.

class Solution {
    public static int[] findTwoNonRepeating(int[] arr) {
        int xor = 0;
        for (int x : arr) xor ^= x;          // twins cancel, a ^ b is left

        int pick = xor & -xor;               // lowest bit where a and b differ

        int a = 0, b = 0;
        for (int x : arr) {
            if ((x & pick) != 0) a ^= x;     // team with that bit on
            else b ^= x;                     // team with that bit off
        }
        return a < b ? new int[]{a, b} : new int[]{b, a};
    }
}

How long it takes: two walks over the array, O(n). Extra room: four ints, O(1).

Watch out for

• xor & -xor keeps the lowest 1. It works for every int, even when xor is Integer.MIN_VALUE.
• Starting a or b at something other than 0. XOR with 0 changes nothing, so 0 is the only safe start.
• Forgetting the order. The two loners come out in whatever order the split gives, so sort the pair if the problem asks.

What interviewers ask next

• Only one loner and everything else in pairs? XOR all of them. The answer is what is left.
• Every number shows up three times except one? Count the 1s at each of the 32 bit positions. Where the count is not a multiple of 3, the loner has a 1. That is O(32 n) time and O(1) room.
• One number is missing from 1 to n and one is repeated? XOR the array with 1 to n. Now the two you want behave like loners, so split by a bit the same way.
• Why does -x share only the lowest 1 with x? -x is ~x + 1. Adding 1 to ~x carries through the trailing 1s of ~x and stops exactly at the lowest 1 of x.

Remember this

Grown-up words: the mixing bowl is XOR, twins vanishing is x ^ x = 0, the thing the loners do not share is a set bit of a ^ b, and xor & -xor isolates the lowest set bit using two's complement.