its bit complicated but I think it will work....correct me if I am
wrong......
In further explanation R stands for repeating number and M stands for
missing number.
step 1 : calculate RESULT = n(n+1)/2 - sum of all set element ..... which
is equal to | M - R | .
if RESULT < 0 then R > M.
if RESULT > 0 then R < M.
step 2 : Now XOR of all the set elements with XOR of 1 to n will give - R
XOR M.
step 3 : for each i in 1 to n
do
k = i XOR R XOR M // R xor M is calcualted
in step 2.
if k - i == RESULT // RESULT is
calculated in step 1.
then K and i are R and M . // We can easily figure
out whether k == R or K==M by looking at the sign of K-i.
Here all the steps take O(n) time complexity and O(1) space complexity.
On Sun, Nov 18, 2012 at 7:31 PM, shady <sinv...@gmail.com> wrote:
> Given an array of size n, which has all distinct elements between 1 to n
> with one element repeating, which also implies that one element is missing.
> How to find the repeating element without using extra space and linear
> time complexity ?
>
> Any way to do it with exor ? :P
>
> --
>
>
>
--
