@shashikant.......the question is different than the link that you have given......please read once again
On Sun, Nov 18, 2012 at 10:32 PM, shashi kant <shashiski...@gmail.com>wrote: > 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 <rushi4...@gmail.com>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 <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 >>> >>> -- >>> >>> >>> >> >> -- >> >> >> > > -- > > > --
