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