Один в паре

В группе из N человек каждый человек обозначается целым числом. Пары представлены одним и тем же номером. Узнай единственного одинокого человека на вечеринке пар.

Примеры:

Input: N = 5, arr = {1, 2, 3, 2, 1}
Output: 3
Explanation: Only the number 3 is single.

Input: N = 11, arr = {1, 2, 3, 5, 3, 2, 1, 4, 5, 6, 6}
Output: 4
Explanation: 4 is the only single.

Наивный подход: для решения проблемы выполните следующие шаги:

• Отсортируйте массив целых чисел.
• Теперь пройдитесь по массиву, просматривая сразу два элемента. Мы делаем это потому, что числа, присутствующие в паре, будут присутствовать в группе из двух и будут появляться последовательно в отсортированном массиве.
• Когда мы сталкиваемся с группой из двух неодинаковых элементов, минимум из двух элементов или первый элемент группы в отсортированном массиве является единственным элементом в группе пар.

Представление вышеуказанного подхода:

For e.g., we take an array of integers = {1, 1, 2, 3, 2, 3, 4, 5, 6, 5, 4}

After sorting the array becomes = {1, 1,  2, 2,  3, 3,  4, 4,   5, 5,  6}

As we can see, 6 is the single element that doesn’t have its pair. 

The time complexity of this algorithm will be O(N log N), as we are sorting the array of numbers first which is the most expensive operation.

Один в паре с использованием побитового оператора:

Чтобы понять решение этой проблемы, во-первых, мы должны понять побитовый оператор XOR. Таблица истинности XOR приведена ниже для справки:

Truth Table for XOR

To quickly recap a really useful property of XOR: When operated on two same numbers, it returns 0. This property can be easily deduced by the truth table given above. When a number will be XOR’ed with itself the binary representation of both A and B in the above truth table would be the same and result in 0 in bits of all positions.

For Eg:

A number XOR’ed with itself always returns 0.

At the party, we have two numbers that are identical to each other, which belong to the couples. If they are XOR’ed with each other, they will return the answer as 0.   To have a full understanding of the solution, we need to know that XOR is associative, i.e., the order of grouping doesn’t matter when multiple XOR operations are done. For e.g.

The order of grouping doesn’t change the result of the expression.

So, if we XOR all the numbers of attendees with each other, we will obtain the number which doesn’t have its pair.
A pictorial representation of the same concept is given with the example below:

The duplicate numbers when XOR’ed will cancel each other irrespective of the order because of the associative property of XOR.

Следуйте инструкциям, чтобы решить проблему:

• Объявите целочисленную переменную ' x ' с начальным значением 0.
• Перебрать массив чисел, представляющих участников, и
  • Продолжайте обновлять «x» с каждой итерацией после выполнения XOR с текущим элементом.
• Целое число ' x ' представляет единственного Участника на вечеринке.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N), где N — размер массива, так как мы проходим через массив один раз.
Вспомогательное пространство: O(1)