Lonely Integer

You are given an array of integers arr in which every element appears exactly twice, except for one element which appears exactly once. Find and return that single ("lonely") element.

Your solution should run in O(n) time using O(1) extra space (i.e. you may not use a hash set/map or sort the array to solve it — use bitwise operations instead).

Example 1

Input: arr = [1, 2, 3, 2, 1]
Output: 3
Explanation: 1 and 2 each appear twice; 3 appears once.

Example 2

Input: arr = [7, 7, 4]
Output: 4
Explanation: 7 appears twice; 4 appears once.

Constraints

• 1 <= arr.length <= 10^5 (arr.length is always odd)
• 0 <= arr[i] <= 10^6
• Every element appears exactly twice, except for one element which appears exactly once.