this is because I have XORed elements. I assumed, in the array there are numbers from 1 to n and a number is repeated once, all others occur once only. So when I XORed the result with numbers from 1 to n(second loop), this will make the numbers XORed twice except the number which was repeated( and now XORed thrice).
so repeated element is given by the result. e.g. say numbers are : 1,2,3,4,5,6,5 XOR them together, let result is Res. Now XOR Res with Natural no.s 1-6. The situation now is : 1 ^ 1, 2 ^ 2,3 ^ 3, 4 ^ 4, 5 ^ 5 ^ 5, 6 ^ 6. So as is clear from above, the result will be 5 and thus algo will not work if the numbers are not in the range 1-n. But you can modify it for a given set of numbers, but the condition is all the elements within that range have to be present in any order with a duplicate one. In this case, find the minimum and maximum, in O(n) time. then follow the procedure mentioned in my earlier post. *Regards Sanju Happy to Help :)* On Fri, Aug 19, 2011 at 5:52 AM, priya ramesh < [email protected]> wrote: > @sanjay: Why doesn't your algo work if the nos are not in the range 1-n?? > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
