Finding an integer that repeats odd number of times in an array of positive integers | Code Samurai

Finding an integer that repeats odd number of times in an array of positive integers | Code Samurai

Finding an integer that repeats odd number of times in an array of positive integers

Question: in an array of positive integers, all but one integer repeats odd number of times. Can you find that integers in O(n) time complexity?

Answer: in order to solve this problem in O(n) time, we need to use bitwise manipulation. Since there is only one integer that repeats odd number of times, we can use the XOR operator to find out that number. When a number XOR with itself, it will become 0. Thus, if a number appears a even number of times, it yield a result of 0. For example, given the array {2, 3, 2, 3}, we have 2 and 3 repeat two times (even). Thus, if we XOR all of them together we should get 0 as the result. However, if there is an odd repeated number, the result will be the value of that number! Here is the algorithm in C++:

Read full article from Finding an integer that repeats odd number of times in an array of positive integers | Code Samurai