Эквивалентные функции, чтобы найти один и единственный элемент, который встречается нечетные времена в данном массиве целых чисел

Question

У меня есть простой вопрос для ruby.

Следующий метод возвращает элемент, который встречается нечетно в данном массиве целых чисел. Гарантируется, что существует один и единственный элемент, который встречается нечетные времена.

seq.detect { |n| seq.count(n).odd? }

Еще одно краткое решение заключается в следующем:

seq.reduce(:^)

Мне нужно объяснение последнего подхода.

Answer 1

Ну, ^ это Xor метод.

1 ^ 1 = 0, 1 ^ 1 ^ 1 = 0 ^ 1 = 1, 1 ^ 2 = binary(01) ^ binary(10) = binary(11) = 3

Таким образом, с помощью Reduce вы пересекаете массив и применяете операцию xor.

Итак, результат xor элементов, который встречается четное время, равен 0, а результатом xor элементов, который встречается нечетное время, является сам элемент.

Итак, общий результат xor - это элемент, который встречается нечетное время.

Например, у вас есть arr = [2, 3, 3, 5, 2, 7, 5]

Когда вы звоните arr.reduce(:^), он работает аналогично следующим образом:

((((((2 ^ 3) ^ 3) ^ 5) ^ 2) ^ 7) ^ 5)

Тогда xor удовлетворяет коммутативному закону и ассоциативному закону, поэтому он эквивалентен следующему

(2 ^ 2) ^ (3 ^ 3) ^ (5 ^ 5) ^ 7 = 0 ^ 0 ^ 0 ^ 7 = 7

Итак, вы найдете ответ 7

Answer 2

Ваша предпосылка неверна. Они дают разные результаты:

seq = [1,2,3,2]
seq.detect { |n| seq.count(n).odd? }  # => 1
seq.reduce :^  # => 2

Вы видите, что ответы разные и что ответ последнего даже не корректен по критериям фильтрации.

Я думаю, что целью было использовать факты о том, что ^ (XOR) является транзитивным, что x^x == 0 для всех x и x^0 == x для всех x. Следовательно, все значения, встречающиеся четное число раз, должны аннулироваться. Проблема заключается в том, что XOR двух или более других значений дает одно из значений в списке, то есть 1^3 == 2.

---

Дополнительное ограничение устраняет проблему, описанную выше. Если одно и только одно значение встречается нечетное количество раз, то оно не может быть XORed с другим нечетным вхождением для создания столкновения. Все четные вхождения самоуничтожаются, оставляя только одно нечетное вхождение XOR с нулем, т. Е. Нечетное вхождение.