I fail to see how any of them work in the general case. In fact, I don't even see them working with range restrictions for n. Also what is the missing number you are talking about? The question is to find the repeated number. As I said before, its an element uniqueness problem whose lower bound is proven to be n log n. So, an O(n) solution does not exist in the general case.
On Thu, Feb 17, 2011 at 1:07 PM, bittu <shashank7andr...@gmail.com> wrote: > @^^ many solution to this problem in O(n) > > METHOD 1(Use sum formula) > > Algorithm: > > 1. Get the sum of numbers > total = n*(n+1)/2 > 2 Subtract all the numbers from sum and > you will get the missing number. > > Time Complexity: O(n) > > > METHOD 2(Use XOR) > > 1) XOR all the array elements, let the result of XOR be X1. > 2) XOR all numbers from 1 to n, let XOR be X2. > 3) XOR of X1 and X2 gives the missing number. > > > Time Complexity: O(n) > > Correct me If I am Wrong > > Thanks & Regards > Shashank Mani >> ""The best way to escape from a problem is to solve > it."" > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
