Find Odd Occurrence

# Find Odd Occurrence ## Difficulty Easy ## Tags `bit manipulation`, `array` ## Problem Statement Given an array of integers where every integer appears an even number of times except for one integer which appears an odd number of times, find that single integer. ## Constraints - The array is non-empty. - There is exactly one number that occurs an odd number of times. - Time complexity should be O(N). - Space complexity should be O(1). ## Signatures ### Python ```python def find_odd(arr: List[int]) -> int: pass ``` ### Java ```java public class Solution { public int find_odd(List<Integer> arr) { return null; } } ``` ### Csharp ```csharp public class Solution { public int find_odd(IList<int> arr) { throw new NotImplementedException(); } } ``` ### Cpp ```cpp class Solution { public: int find_odd(vector<int> arr) { } }; ``` ### C ```c int find_odd(int* arr) { } ``` ### Ruby ```ruby def find_odd(arr) end ``` ### Perl ```perl sub find_odd { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def find_odd(arr: List[Int]): Int = { } } ``` ### Haskell ```haskell find_odd :: ... -> ... find_odd args = undefined ``` ### Clojure ```clojure (defn find_odd [arr] ) ``` ### Scheme ```scheme (define (find_odd arr) ) ``` ## Examples ### Example 1 **Input:** ``` arr = [1, 2, 3, 2, 1] ``` **Output:** ``` 3 ``` **Explanation:** 1 and 2 each appear twice. 3 appears once (odd). ### Example 2 **Input:** ``` arr = [4, 3, 3, 4, 4, 4, 5] ``` **Output:** ``` 5 ``` **Explanation:** 4 appears 4 times, 3 appears 2 times, 5 appears 1 time (odd). ### Example 3 **Input:** ``` arr = [7, 7, 7] ``` **Output:** ``` 7 ``` **Explanation:** 7 appears 3 times (odd). ## Hints 1. Recall the properties of the XOR (`^`) operation. 2. `A ^ A = 0` and `A ^ 0 = A` 3. What happens if you XOR all elements in the array?