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?

Solutions
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!

Code in java

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

c implementation

int getOddOccurringNumber(int arr[], int arr_size)
{
     int i;
     int result= 0; 
     for (i=0; i < arr_size; i++)     
        result= result^ arr[i];
      
     return result;
}

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.

The caret '^' sign means XOR (exclusive OR). And, our algorithm works because XOR of two same number is 0. For example, 2 XOR 2 = 0 because 0010 XOR 0010 = 0000. Thus, all the even repeating numbers will yield the result = 0 while the odd repeating number will yield itself as the result. In our example, we know 3 is the odd-repeating number because 3 XOR 0 = 3.

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.

Approach 2 - Using the hash table
For example, we can use a hash table to maintain counts of repetition for each number in the array. Then, we look for the number with odd count.But what if someone asks "not to use any datastructure" / additional storage.

Thanks. Please let me know if you have better solution