Finding first non-repeating number in integer array

Question

I got this question for an exam:

Given an integer array find the first number which is not repeating in array using O(N) time complexity and O(1) space complexity.

I couldn't think of any solution. I know I can iterate over the array and maintain a linkedhashmap which will store both array element and number of times it appears and then in the end I have to search hashmap to find that number. Space complexity is greater than O(1) but I couldn't think of other solution.

I also read problem carefully and the said that max size of array would be 1million. I think if we can create a custom hashmap which will utilise an fixed size array of 1 million size then this can be achieved in O(1) space complexity as in that case storage required would be constant but nore sure if I am correct. Please let me know if there is any other solution.

Answer 1

If there are exactly TWO (or in multiples of 2) entries for all elements except one element, which will be non-repeating, you can use XOR operator.

Example:

int x=arr[0];
for(i=1;i<1000;i++)
  x^=a[i];
printf("Non-repeating: %d",x);

Any number XORed with itself is 0. So, if any number appears twice it will be 0 in the overall XOR result, thus leaving only the non-repeating number in x.

Note: If you have 1 million numbers, the variable to store the XOR result must be large enough.

Answer 2

To find first non-repeating number in given integer array

UPDATE: Found a better solution. I think we can solve it in O(n) time complexity using an additional data structure such as HashMap. Iterate through the array, and put the element as key and the element's index position in array as the value in the map. if the key already exists, can either remove the key-value pair or just set the value to -1. Once the entire array is traversed, then we can get the keySet() from the hashmap, and then find the key which has lowest value(ignore -1). so this would be Time Complexity: O(N) Space Complexity: O(N)

Old solution: We can solve this by, creating another array which is obtained by sorting the given array. This would take O(nlogn) time. then we can iterate through each element in given input array, try to find the element & compare with next element in the sorted array, if repeated continue for the next element in given array, if not repeated, then we found the first non-repeating element in given input array of integers.

time complexity: O(nlogn)
space complexity: O(n)

P.S: I am sorry, hadn't read all the comments, James Kanze has already provided this solution in comments, credits to him.