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++:

  public int getIntOddlyOccured(int[] inputArr)
  {
    int oddNum = inputArr[0];
   
    for(int i = 1; i < inputArr.length; i++)
      oddNum = oddNum ^ inputArr[i];
   
    return oddNum;
  }

Explanation: our method takes an integer array as argument. It assumes that there is one and only one odd occurring number (conditions given by the question), so it will return that number and does no validation to see whether the input in fact has only one odd repeated number. In the body, the method loops through the array and XOR all the elements together. The result will be the oddly repeated number.

Example: let's do an example with this array {1, 4, 3, 4, 1}. The method first initializes the result oddNum to 1 and then does the for loop:

1. First iteration: oddNum = 1(0001) ^ 4(0100) = 5(0101) and i = 1
2. Second iteration: oddNum = 5(0101) ^ 3(0011) = 6(0110) and i = 2
3. Third iteration: oddNum = 6(0110) ^ 4(0100) = 2(0010) and i = 3
4. Fourth iteration: oddNum = 2(0010) ^ 1(0001) = 3(0011) and i = 4
5. Loop ends because i = 5, so we return oddNum = 3 which is the oddly repeated number in the array

This algorithm takes O(n) time complexity because it loops through the array only once. The space complexity is O(1) because we only need an additional integer for storage. Very efficient! That's all we have for now. Thanks for reading :)