check this link....it has many different solutions to this problem http://www.geeksforgeeks.org/archives/7953
*Shashi Kant * ***"Think positive and find fuel in failure"* *+917259733668 * http://thinkndoawesome.blogspot.com/ *System/Software Engineer* *Hewlett-Packard India Software Operations. * On Sun, Nov 18, 2012 at 8:16 PM, Rushiraj Patel <[email protected]> wrote: > 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 <[email protected]> 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 >> >> -- >> >> >> > > -- > > > --
