Repeating number in array
In last post : Find missing number in array, we learned how to find a missing number in array of integers with values in a given range. Today, we will learn how find a repeating number in array of integers from 1 to n. Note that here also, numbers are not sorted but are confined to a range. So, if size of array is N, then range of numbers is from 1 to N-1 as one integer will be repeated. Examples :
A = [1,2,3,3,4,5]. Repeating number is 3 Size of array : 6 Range : 1 to 5
As we seen in case of finding missing number, XOR principle can be applied here too. Why? Because in this case repeated number will be XORed with itself three times. Below are properties of XOR, this makes things clear automatically.
A XOR A = 0 0 XOR A = A
Now, when a number XORed with itself, result is zero, and when zero is XORed with number, result is number. Extending this, if we XORed same number thrice or without generality, odd number of times, result will be the number itself.
Using odd number of times XOR principle, algorithm to find repeating number in array.
1. XOR all actual numbers in array. Call it actualXOR. 2. XOR all numbers in range 1 to N-1. Call it expectedXOR 3. XOR actualXOR with expectedXOR. Result will be repeating number.
This is because all numbers except repeating numbers will be XORed even number of times, and cancel each other. Since repeating number will be XORed thrice, final result will be repeating number. Let’s take above example and see if it works
A = [1,2,2,3,4] actualXOR = 001 XOR 010 = 011 XOR 010 = 001 XOR 011 = 010 XOR 100 = 110 expectedXOR = 001 XOR 010 = 011 XOR 011 = 000 XOR 100 = 100 ActualXOR XOR expectedXOR = 110 XOR 100 = 010
Repeating number in array implementation
Complexity of XOR method to find repeating number in array is O(n).
Please share your thoughts through comments, if you see something is missing or wrong or not explained properly.