Определение отсутствующего элемента в массиве после удаления

Условие

Имеются два массива:

1. Исходный массив, содержащий набор чисел.
2. Массив‑копия первого, из которой удалено ровно одно число. Необходимо написать функцию, которая определит и вернёт удалённое значение.

public class Numbers {
    public static void main(String[] args) {
        assert(diff(new int[]{4, 2, 3, 6}, new int[]{2, 3, 4}) == 6);
        assert(diff(new int[]{1, 2, 2}, new int[]{2, 1}) == 2);
    }

    private static int diff(int[] beforeRemove, int[] afterRemove) {
        //todo: not implemented
    }
}

Ответ

Выполните XOR всех элементов обоих массивов: одинаковые значения взаимно уничтожатся, останется удалённое число. Это работает и с повторяющимися целыми числами.

private static int diff(int[] beforeRemove, int[] afterRemove) {
    int result = 0;
    for (int value : beforeRemove) result ^= value;
    for (int value : afterRemove) result ^= value;
    return result;
}

Время O(n), дополнительная память O(1), переполнения суммы нет. Решение опирается на гарантию, что удалён ровно один элемент и других изменений не было. Сам XOR не проверяет эту гарантию: для произвольных различий массивов он не является валидатором.